问题描述：
给定一个2D网格，每个单元格要么是墙"W"，要么是敌人"E"或空的"0"(数字0)，返回你可以用一枚炸弹杀死的最大敌人。
炸弹从埋设点开始杀死同一行和同一列的所有敌人，直到它击中墙壁，因为墙壁太坚固了，无法摧毁。
注意，你只能把炸弹放在空牢房里。
Example:
For the given grid
0 E 0 0
E 0 W E
0 E 0 0
return 3. (Placing a bomb at (1,1) kills 3 enemies)
我的DFS解决方案：
def maxKilledEnemies(grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
l_row, l_col = len(grid), len(grid[0])
visited = [[False] * l_col for _ in range(l_row)] #using this array to avoid duplicate traverse.
def dfs(i, j):
if 0 <= i < l_row and 0 <= j < l_col and not visited[i][j]:
visited[i][j] = True
if grid[i][j] == 'W': #wall return 0
return 0
elif grid[i][j] == '0': #0 means we just ignore this cell and traverse it adjacents
top_val = dfs(i - 1, j)
down_val = dfs(i + 1, j)
left_val = dfs(i, j - 1)
right_val = dfs(i, j + 1)
return left_val + right_val + top_val + down_val
elif grid[i][j] == 'E': # Enemy and we add it by 1
top_val = dfs(i - 1, j)
down_val = dfs(i + 1, j)
left_val = dfs(i, j - 1)
right_val = dfs(i, j + 1)
return left_val + right_val + top_val + down_val + 1
return 0
ret = [0]
for i in range(l_row):
for j in range(l_col):
if not visited[i][j] and grid[i][j] == '0':
val = dfs(i, j)
ret[0] = max(val, ret[0])
return ret[0]
Solution().maxKilledEnemies([["0","E","0","0"],["E","0","W","E"],["0","E","0","0"]]) #return 4 but expect 3.
这个想法很简单，对于num为0的每个单元格，我们遍历它4方向(上/下/左/右)。
我知道还有其他方法可以更聪明地解决这个问题。但我想弄清楚为什么我的方式不起作用？
您的代码中至少有三个错误：
- 在每个递归步骤中，您都会探索所有可能的方向。这使得你的搜索行为像洪水填充，但你想从你只检查的炸弹位置向各个方向开始。之后，在给定的方向上递归(或迭代搜索)
- 你没有检查可能的炸弹位置是否是空的，所以你的代码可以把炸弹放在敌人身上
- 您不会在搜索之间重置已访问的数组，因此实际上只评估单元格(0，0)
一个解决方案是具有两个功能，
- 一个用于可能的炸弹位置。请在此处检查单元格是否为空。如果是，则按北、东、南和西的顺序计算受害者人数
- 一个是炸弹的"射线"。沿着指定的方向行进，数敌人，直到你撞到墙上。因为光线只在一个方向上传播，所以不再需要访问的阵列
这不是真正的深度优先搜索，所以您可以使用循环，而不是递归地调用第二个函数。
可能是因为使用DFS不是一个解决方案。当你使用DFS时，你会搜索网格中所有可到达的空间，但对于你的问题，你应该只搜索直接的水平或垂直空间。例如：在[0][0]处使用DFS时，您会发现所有敌人，而不仅仅是[0][1]和[1][0]处的敌人。