LeetCode上哈密尔顿路径
来源:9-6 Leetcode 上的哈密尔顿问题
GameCater
2021-08-29
波波老师,为什么我用全局变量cnt接收递归结果,答案就不对呢,我用您的方式改了一下我的代码,答案是对的,说明其他逻辑没有问题,只在dfs中接收结果那儿出了问题,而且我在纸上也搞了个小例子单步调试过了,就是搞不清楚为什么我的方式不对
public class Solution0980 {
private int[][] grid;
private int R, C;
private int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
private boolean[] visited;
private int left;
private int start;
private int cnt; // 记录路径数量
public int uniquePathsIII(int[][] grid) {
this.grid = grid;
R = grid.length;
C = grid[0].length;
left = R * C;
for (int i = 0; i < R; i ++) {
for (int j = 0; j < C; j ++) {
if (grid[i][j] == 1) {
start = i * C + j;
grid[i][j] = 0;
}
else if (grid[i][j] == -1) {
left --; // 记录真实的可以通过的方格的数量
}
}
}
visited = new boolean[R * C];
dfs(start);
return cnt;
}
int dfs(int v) {
visited[v] = true;
left --;
int vx = v / C, vy = v % C;
if (grid[vx][vy] == 2 && left == 0) {
visited[v] = false;
left ++;
return 1;
}
for (int d = 0; d < 4; d ++) {
int nextx = vx + dirs[d][0];
int nexty = vy + dirs[d][1];
if (validateVertex(nextx, nexty) && !visited[nextx * C + nexty] &&
grid[nextx][nexty] != -1) {
cnt += dfs(nextx * C + nexty);
}
}
visited[v] = false;
left ++;
return 0;
}
private boolean validateVertex(int x, int y) {
return x >= 0 && x < R && y >= 0 && y < C;
}
public static void main(String[] args) {
int[][] grid = {{0,0,0},{0,0,1},{-1,2,-1}};
int[][] grid2 = {{0, 1},{2, 0}};
System.out.println(new Solution0980().uniquePathsIII(grid));
}
}
写回答
1回答
-
神奇了。
对于这段代码,如果把这句话:
cnt += dfs(nextx * C + nexty);
拆成两句:
int t = dfs(nextx * C + nexty); cnt += t;
就是正确的。
我暂时没有搞明白为什么。我找时间研究一下。你要是搞明白了,也请告诉我一下。谢谢!
012021-09-04
相似问题