这个DFS解决方案有什么问题？

Question

问题描述：

你想在一片空旷的土地上建造一座房子，它能在最短的距离内到达所有建筑物。你只能上下左右移动。将为您提供一个值为0、1或2的二维网格，其中：

每一个0代表一块你可以自由通行的空地。 每一个1代表一个你不能通过的建筑。 每两个标记一个你不能通过的障碍。 例如，给定（0,0）、（0,4）、（2,2）处的三座建筑物和（0,2）处的一个障碍物：

1 - 0 - 2 - 0 - 1
|   |   |   |   |
0 - 0 - 0 - 0 - 0
|   |   |   |   |
0 - 0 - 1 - 0 - 0

点（1,2）是建造房屋的理想空地，因为3+3+1=7的总行程最小。所以返回7

我用BFS方法解决了这个问题。然后我想用DFS的方法解决它，但是被卡住了。下面是我的代码：

class Solution(object):
    def shortestDistance(self, grid):
        """
        :type grid: List[List[int]]
        :rtype: int
        """
        rl, cl = len(grid), len(grid[0])
        builds = sum([col for row in grid for col in row if col == 1])
        dist, hit = [[0] * cl for _ in range(rl)], [[0] * cl for _ in range(rl)]

        def dfs(x, y, step):
            '''
            Wrong answer, it seems result dist alway keep the longest distance?
            '''
            if 0 <= x < rl and 0 <= y < cl and not visited[x][y]:
                visited[x][y] = True
                if grid[x][y] == 0:
                    dist[x][y] += (step + 1)
                    hit[x][y] += 1

                    dfs(x - 1, y, step + 1)
                    dfs(x + 1, y, step + 1)
                    dfs(x, y - 1, step + 1)
                    dfs(x, y + 1, step + 1)

        def bfs(x, y):
            '''
            works properly
            '''
            visited = [[False] * cl for _ in range(rl)]
            queue =[(x, y, 0)]
            while queue:
                k, m, step = queue.pop(0)
                for i, j in ((k - 1, m), (k + 1, m), (k, m - 1), (k, m + 1)):
                    if 0 <= i < rl and 0 <= j < cl and not visited[i][j]:
                        visited[i][j] = True
                        if grid[i][j] == 0:
                            dist[i][j] += (step + 1)
                            hit[i][j] += 1

                            queue.append((i, j, step + 1))
        for i in range(rl):
            for j in range(cl):
                if grid[i][j] == 1:
                    # bfs(i, j) # this works properly
                    visited = [[False] * cl for _ in range(rl)]
                    dfs(i - 1, j, 0)
                    dfs(i + 1, j, 0)
                    dfs(i, j - 1, 0)
                    dfs(i, j + 1, 0)

        ret = float('inf')
        for i in range(rl):
            for j in range(cl):
                if grid[i][j] == 0 and hit[i][j] == builds:
                    ret = min(ret, dist[i][j])
        return ret if ret != float('inf') else -1

# expect 7
print Solution().shortestDistance([[1,0,2,0,1],[0,0,0,0,0],[0,0,1,0,0]])

这是一种典型的图搜索问题。通常可以用DFS和BFS两种方法求解。就是不知道怎么用DFS的方式解决

Answer 1

简单地说，DFS并不是为了寻找最短路径。有了一些回溯和谨慎的标记和取消标记的visted节点，你可以用它找到所有路径到达一个给定的点，并选择最短的一个，但它是不必要的复杂和方式慢于BFS