LeetCode上哈密尔顿路径

Question

波波老师，为什么我用全局变量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));
	}
}

Answer 1

liuyubobobo 2021-09-03 12:41:03

神奇了。

对于这段代码，如果把这句话：

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

拆成两句：

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

就是正确的。

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

• 提问者 GameCater #1

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