LeetCode--980. Unique Paths III

这个问题与Unique Paths和Unique Paths II都属于同一类问题，但有所不同。它要求从指定起点出发经过每一个可通行的格点，然后到达指定终点的路径总数。
开始想到的就是暴力搜索的方式，代码的基本结构与它的姊妹题基本一致，但是返回条件和参数却不一样，代码如下：

class Solution {public static int n_row;public static int n_col;public static int start_row;public static int start_col;public static int end_row;public static int end_col;public static int ret;public int uniquePathsIII(int[][] grid) {int num=0;n_row=grid.length;n_col=grid[0].length;ret=0;for(int i=0;i<n_row;i++){for(int j=0;j<n_col;j++){if(grid[i][j]==1){start_row=i;start_col=j;}else if(grid[i][j]==2){end_row=i;end_col=j;num++;}else if(grid[i][j]==0)num++;elsecontinue;}}dfs(num,start_row,start_col,grid);return ret;}public static void dfs(int n,int row,int col,int[][] grid){if(row==end_row && col==end_col){if(n==0)ret++;return;}for(int dx=-1;dx<=1;dx++){for(int dy=-1;dy<=1;dy++){if(Math.abs(dx+dy)==1 && canPass(row+dx,col+dy,grid)){grid[row+dx][col+dy]=3;dfs(n-1,row+dx,col+dy,grid);grid[row+dx][col+dy]=0;}}}}public static boolean canPass(int i,int j,int[][] grid){return (i>=0 && i<n_row) && (j>=0 && j<n_col) && grid[i][j]%2==0;//是否为可以通过的格点条件：1位置合法 2没有被当前路径经过过}
}

看Solutions发现里面的解法一与上述方法一致，解法二使用了位技巧实现访问信息的编码作用：位操作的解法看起来十分晦涩

class Solution {int ans;int[][] grid;int R, C;int tr, tc, target;int[] dr = new int[]{0, -1, 0, 1};int[] dc = new int[]{1, 0, -1, 0};Integer[][][] memo;public int uniquePathsIII(int[][] grid) {this.grid = grid;R = grid.length;C = grid[0].length;target = 0;int sr = 0, sc = 0;for (int r = 0; r < R; ++r)for (int c = 0; c < C; ++c) {if (grid[r][c] % 2 == 0)target |= code(r, c);if (grid[r][c] == 1) {sr = r;sc = c;} else if (grid[r][c] == 2) {tr = r;tc = c;}}memo = new Integer[R][C][1 << R*C];return dp(sr, sc, target);}public int code(int r, int c) {return 1 << (r * C + c);}public Integer dp(int r, int c, int todo) {if (memo[r][c][todo] != null)return memo[r][c][todo];if (r == tr && c == tc) {return todo == 0 ? 1 : 0;}int ans = 0;for (int k = 0; k < 4; ++k) {int nr = r + dr[k];int nc = c + dc[k];if (0 <= nr && nr < R && 0 <= nc && nc < C) {if ((todo & code(nr, nc)) != 0)ans += dp(nr, nc, todo ^ code(nr, nc));}}memo[r][c][todo] = ans;return ans;}
}