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回答

liuyubobobo

2021-09-03

神奇了。


对于这段代码,如果把这句话:

cnt += dfs(nextx * C + nexty);


拆成两句:

int t = dfs(nextx * C + nexty);
cnt += t;


就是正确的。

我暂时没有搞明白为什么。我找时间研究一下。你要是搞明白了,也请告诉我一下。谢谢!

0
1
GameCater
着实没搞懂,研究了一下字节码反编译结果,对于这段代码,除了实例变量cnt的值和dfs实例方法的返回值入栈顺序不一样,其他好像本质上都一样,对于cnt += dfs(...),cnt的值先入栈,接着dfs的返回值入栈,然后把栈顶两个值相加,相加的结果赋值回cnt变量;对于使用临时变量t的这种方式,底层是先把dfs返回值压入栈中,然后把栈顶的值(就是dfs的返回值)赋值给本地临时变量t,接着按序压入cnt的值和t的值,并把两个值相加,结果赋值回cnt。不知道我以上的分析对不对
2021-09-04
共1条回复

玩转算法系列--图论精讲(Java版)

30+小时系统学习,bobo带你克服被图论支配的恐惧

1591 学习 · 324 问题

查看课程