0
問題の説明：このDFS溶液で何が問題なのですか？
すべての建物に最も近い距離にある空の土地に家を建てたいとします。上下左右にしか動かすことができません。もし値が0、1又は2の二次元グリッドが与えられる。ここで
それぞれ0マークあなたが自由にすることによって通過することができる空の土地。 各1マーク、あなたが通過することができない建物。 各2あなたが通過することができない障害物をマーク。例えば 、3つの（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の方法でそれを修正する方法を理解できませんか？