问题是:一个人正在二维数组中寻找目标(标记为 9),其中 0 代表墙壁,1 代表道路。该方法应该确定该人是否可以找到目标。
我很容易使用 DFS 提出了解决方案,但在尝试找出代码的时间和空间复杂度时遇到了困难。
public boolean find(int[][] grid) {
if(grid == null || grid.length == 0 || grid[0].length == 0 || grid[0][0] == 0) return 0;
return helper(grid,0,0);
}
private boolean helper(int[][] grid,int x, int y) {
if(x >= 0 && x < grid.length && y >= 0 && y < grid[0].length) {
if(grid[x][y] == 0) return false;
else if(grid[x][y] == 9) return true;
else if(grid[x][y] == 1) {
grid[x][y]=2;
return helper(grid,x,y-1) || helper(grid,x+1,y) || helper(grid,x,y+1) || helper(grid,x-1,y);
}
else return false;
}
else return false;
}
我认为时间和空间复杂度是O(mn),但我不确定。
最佳答案
一般来说,DFS 的时间复杂度为 O(m + n),空间复杂度为 O(n),其中 n 是您可以位于的位置数,m 是位置之间的连接总数(如果您熟悉图论,则 n 是节点数,m 是边数)。在您的情况下,如果您有一个大小为 w × h 的网格,则 n = wh (每个网格位置可以有一个位置)并且 m ≤ 4wh (因为每个位置最多与其他四个位置相邻)。这意味着运行时间将为 O(wh),空间复杂度也将为 O(wh)。
关于java - 迷宫寻路时递归DFS的时间和空间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33966965/