980. Different path III DFS

980. Different paths III

On a two-dimensional grid  grid  On , Yes 4 Two types of squares ：

• 1  Represents the starting square . And there's only one starting square .
• 2  Indicates the end square , And there's only one end square .
• 0  An empty square that we can walk through .
• -1  It's an obstacle we can't cross .

Return in four directions （ On 、 Next 、 Left 、 Right ） When you go up , The number of different paths from the start square to the end square .

Every barrier free square has to pass once , But you can't go through the same grid repeatedly in a path .

Example 1：

 Input ：[[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
 Output ：2
 explain ： We have two paths ：
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)

Example 2：

 Input ：[[1,0,0,0],[0,0,0,0],[0,0,0,2]]
 Output ：4
 explain ： We have four paths ： 
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)

Example 3：

 Input ：[[0,1],[2,0]]
 Output ：0
 explain ：
 There is no way to go through every empty square completely once .
 Please note that , The start and end squares can be located anywhere in the grid .

Tips ：

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

The result of doing the question

success

Method ：DFS

1. Find the starting point , Final position , Number of open spaces

2. Start from the starting point and try each path in turn , The occupied space is modified to 1, Try to revert back to 0

class Solution {
    public int uniquePathsIII(int[][] grid) {
        int[] start = null;
        int[] end = null;
        int m = grid.length;
        int n = grid[0].length;
        int empty = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                switch(grid[i][j]){
                    case 0: {++empty; break;}
                    case 1: start = new int[]{i,j}; break;
                    case 2: end = new int[]{i,j}; break;
                }
            }
        }

        dfs(start,end,grid,empty);
        return ans;
    }
    int ans = 0;
    int[] directions = new int[]{0,1,0,-1,0};
    private void dfs(int[] start, int[] end,int[][]grid,int empty){
        int m = grid.length;
        int n = grid[0].length;
        for(int i = 0; i < 4; i++){
            int x = start[0]+directions[i];
            int y = start[1]+directions[i+1];
            if(x>=0&&x<m&&y>=0&&y<n){
                if(empty == 0){
                    if(x==end[0]&&y==end[1])++ans;
                }else{
                    if(grid[x][y]==0){
                        grid[x][y]=1;
                        dfs(new int[]{x,y},end,grid,empty-1);
                        grid[x][y]=0;
                    }
                }
            }
        }
    }
    
}