leetcode 980. 不同路径 III(Unique Paths III)

在二维网格 

grid

 上，有 4 种类型的方格：

• 1

   表示起始方格。且只有一个起始方格。

• 2

   表示结束方格，且只有一个结束方格。
•  表示我们可以走过的空方格。

• -1

   表示我们无法跨越的障碍。

返回在四个方向（上、下、左、右）上行走时，从起始方格到结束方格的不同路径的数目，每一个无障碍方格都要通过一次。

示例 1：

输入：[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
输出：2
解释：我们有以下两条路径：
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)      

示例 2：

输入：[[1,0,0,0],[0,0,0,0],[0,0,0,2]]
输出：4
解释：我们有以下四条路径： 
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)      

示例 3：

输入：[[0,1],[2,0]]
输出：0
解释：
没有一条路能完全穿过每一个空的方格一次。
请注意，起始和结束方格可以位于网格中的任意位置。
      

提示：

1. 1 <= grid.length * grid[0].length <= 20

这数据规模很小，不用什么剪枝都可以过把，这里只剪了大于cnt的搜索，不过cnt已经是全部搜索了，等于没剪，下面这个博客介绍了奇偶剪枝，路径剪枝

HDU 1010 Tempter of the Bone （dfs+奇偶剪枝+路径剪枝）

class Solution {
	boolean[][] vis;
	int n,m,ans=0,cnt=0,x1,y1,x2,y2;
	int[] dx = new int[] {1,0,-1,0};
	int[] dy = new int[] {0,1,0,-1};

	
    void dfs(int[][] grid,int x,int y,int t) {
    	if(t>cnt)
    		return;
    	if(x==x2 && y==y2) {
    		if(t==cnt)
    			ans++;
    		return;
    	}
    	
    	for(int i=0;i<4;i++) {
    		int u = x + dx[i];
    		int v = y + dy[i];
    		if(u>=0 && u<n && v>=0 && v<m && grid[u][v]!=-1 && !vis[u][v]) {
    			vis[u][v] = true;
    			dfs(grid,u,v,t+1);
    			vis[u][v] = false;
    		}
    	}

    }
	
    public int uniquePathsIII(int[][] grid) {
        n = grid.length;
        m =grid[0].length;
        vis = new boolean[n][m];
        
    	for(int i=0;i<n;i++)
    		for(int j=0;j<m;j++) {
    			vis[i][j] = false;
    			if(grid[i][j]==0)
    				cnt++;
    			else if(grid[i][j]==1) {
    				x1 = i;
    				y1 = j;
    				cnt++;
    			}else if(grid[i][j]==2){
    				x2 = i;
    				y2 = j;
    				cnt++;
    			}
    		}
    	vis[x1][y1]=true;
    	dfs(grid,x1,y1,1);
    	return ans;
    }
    
}