Number of Ways Fully Traverse a Matrix

Link

4、一个4*5迷宫里，给定起点终点和障碍，有多少种方法能够从起点走到终点，并把所有的非障碍点都走过。最开始是四个方向，然后问如果八个方向怎么办 ，如果是国际象棋皇后怎么办

 

第四题给的数据规模很小，是不是就是dfs暴力就可以了？

嗨，楼主，最后一题有步数限制嘛？如果没步数限制的话岂不是可以有无数种可能了吗？把所有非障碍点走一遍

10000

00***

00002

 

上图中，1是起点，星号是障碍物，2是终点，这种情况下，如果还得把所有非障碍点都走过一遍的话，第一行的第二列，第三列，第四列都得走两遍，

那上图还是一个VALID的INPUT吗？ 如果是的话，就代表一个点可以走无数遍，如果一个点可以走无数遍，那答案不久无穷大了吗？

 

我写的dfs 然后followup那里的话复杂度爆炸了

 

就是每个点走过且只走一遍，步数是定死的

这个题，要求总共多少种走法，听起来像是动规了。

但是，走的方向是四个方向。没有明显看起来可以递归求解的地方，不知道从哪里下手

segment tree可以handle mutable inputs

 

能想到只有backtrack，太brutal force了，如果有toplogical order的话应该可以用dp

 

是不是可以四维状压dp？dp[x][y][step][state]，起始状态dp[x0][y0][0][state1]，终止状态dp[x1][y1][k][state2]。(x0, y0) = 起点，(x1, y1) = 终点，k = 除了起点、终点和障碍外的格子总数目+1，state都是20位二进制，state1 = 把起点位置设为1，state2 = 除了障碍物以外的所有位置都是1。循环最外层按步数从0到k遍历，内层就不用说了。时间复杂度O(20 * 20 * 方向数 * (1 << 20))

 

 

最后一题可以用DP么，或者说dfs + cache.

 

dp[i][j] means from start to {i, j}, how many ways to reach {i,j},  还需要记录访问了多少空点.

 

dp[i][j]  = if ([i-1][j] not visited) + dp[i-1][j]  same to {i + 1, j} {i, j-1} {i, j + 1}.  另外感觉起点和终点有一定的限制, 如果两点是全局 4 * 5 随机的话, 会非常复杂。 这个时候貌似就需要用双向dfs+ cache了。 也就是从起点, 和终点各自开始dfs, 有相交点时, 两个的遍历必须访问了所有空点, 然后走法是相乘。 当然，做这些都是个人猜的，不一定work.

 

最后那个用 dp bitmask？ 毕竟网格很少

如果每个点走过且走以遍，步数是定死的话，步数要求就是所有可以走的点的个数呗。那么就算可以走四个方向，应该也可以动规。

不用记录之前走过哪些点，只用记录现在的位置，和走过的步数。

等步数到了上限的时候，发觉自己还没在终点，就返回0，在终点的话就返回1.因为如果步数又到了上限，人也在终点，那不就是代表所有可以走的点都走过了，而且只走了一遍嘛？

以上思路是DFS+MEMO。

所以是DP[ROW][COL][STEPS]

 

最后一题需要状态压缩，每个状态包含当前坐标x，y以及所有已经走过的点，因为4x5，可以用一个整数表示x，y 以及20个点，如果嫌状态压缩麻烦，可以只压缩所有已经走过的点，可以用一个三维数组保存状态[X][Y][status] 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61

import java.util.*; public class Main { public static void main(String[] args) { System.out.println("heello world"); int[][] matrix = new int[][]{{0,0,0},{0,0,0},{0,0,0}}; Problem pb = new Problem(matrix);; int r = pb.getWays(); System.out.println(r); } } class Problem{ int[][] matrix; int m, n; int[][] dir = new int[][]{{-1,0},{1,0},{0,-1},{0,1}}; int[][][] dp; Problem(int[][] _matrix){ matrix = _matrix; m = matrix.length; n = matrix[0].length; } int getWays(){ int N = m*n; dp = new int[m][n][(int)Math.pow(2,N)]; dp[0][0][1] = 1; int fullState = 0; for(int i=0; i<N; ++i){ fullState |= 1<<i; } for(int i=0; i<m; ++i){ for(int j=0; j<n; ++j){ if(matrix[i][j]==1){//block int k = i*n+j; fullState = fullState & (~(1<<k)); } } } helper(0, 0, 1); return dp[m-1][n-1][fullState]; } void helper(int i, int j, int state){ for(int[] d : dir){ int i0 = i+d[0], j0 = j+d[1]; if(i0>=0 && i0<m && j0>=0 && j0<n && matrix[i0][j0]==0){ int k = i0*n+j0; int mask = 1<<k; if((state&mask) !=0 ) continue;//visited alreay int state0 = state | mask; dp[i0][j0][state0] += dp[i][j][state]; helper(i0, j0, state0); } } } }