You are given an m x n integer array grid where grid[i][j] could be:


	1 representing the starting square. There is exactly one starting square.
	2 representing the ending square. There is exactly one ending square.
	0 representing empty squares we can walk over.
	-1 representing obstacles that we cannot walk over.


Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.

&nbsp;
Example 1:

Input: grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: We have the following 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: grid = [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
Output: 4
Explanation: We have the following 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: grid = [[0,1],[2,0]]
Output: 0
Explanation: There is no path that walks over every empty square exactly once.
Note that the starting and ending square can be anywhere in the grid.


&nbsp;
Constraints:


	m == grid.length
	n == grid[i].length
	1 &lt;= m, n &lt;= 20
	1 &lt;= m * n &lt;= 20
	-1 &lt;= grid[i][j] &lt;= 2
	There is exactly one starting cell and one ending cell.


class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        ans, empty = 0, 1
        
        def dfs(grid: List[List[int]], row: int, col: int, count: int, visited) -> None:
            if row >= len(grid) or col >= len(grid[0]) or row < 0 or col < 0 or grid[row][col] == -1:
                return
            nonlocal ans
            if grid[row][col] == 2:
                if empty == count:
                    ans += 1
                return
            if (row, col) not in visited:
                visited.add((row, col))
                dfs(grid, row + 1, col, count + 1, visited)
                dfs(grid, row - 1, col, count + 1, visited)
                dfs(grid, row, col + 1, count + 1, visited)
                dfs(grid, row, col - 1, count + 1, visited)
                visited.remove((row, col))
        
        row, col = 0, 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    row, col = i, j
                elif grid[i][j] == 0:
                    empty += 1
        dfs(grid, row, col, 0, set())
        return ans
class Solution {
    int walk = 0;
    public int uniquePathsIII(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    walk++;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    return ways(grid, i, j, m, n, 0);
                }
            }
        }
        return 0;
    }
    public int ways(int[][] grid, int cr, int cc, int m, int n, int count) {
        if (cr < 0 || cr == m || cc < 0 || cc == n || grid[cr][cc] == -1) {
            return 0;
        }
        if (grid[cr][cc] == 2) {
            if (count - 1 == walk) return 1;
            return 0;
        }
        grid[cr][cc] = -1;
        int ans = 0;
        int[] r = {0, 1, 0, -1};
        int[] c = {1, 0, -1, 0};
        for (int i = 0; i < 4; i++) {
            ans += ways(grid, cr + r[i], cc + c[i], m, n, count + 1);
        }
        grid[cr][cc] = 0;
        return ans;
    }
}
class Solution {
public:
    int dfs(vector<vector<int>>&grid,int x,int y,int zero){
        // Base Condition
        if(x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size() || grid[x][y] == -1){
            return 0;
        }
        if(grid[x][y] == 2){
            return zero == -1 ? 1 : 0; // Why zero = -1, because in above example we have 9 zero's. So, when we reach the final cell we are covering one cell extra that means if all zero all covered then on reaching final it will make zero count = -1
            // If that's the case we find the path and return '1' otherwise return '0';
        }
        grid[x][y] = -1; // mark the visited cells as -1;
        zero--; // and reduce the zero by 1

        int totalPaths = dfs(grid, x + 1, y, zero) + // calculating all the paths available in 4 directions
            dfs(grid, x - 1, y, zero) +
            dfs(grid, x, y + 1, zero) +
            dfs(grid, x, y - 1, zero);

        // Let's say if we are not able to count all the paths. Now we use Backtracking over here
        grid[x][y] = 0;
        zero++;

        return totalPaths; // if we get all the paths, simply return it.
    }

    int uniquePathsIII(vector<vector<int>>& grid) {
       int start_x,start_y=0,cntzero=0;

        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[0].size();j++){
                if(grid[i][j]==0) cntzero++;
               else if(grid[i][j]==1){
                    start_x=i;
                    start_y=j;
                }
            }
        }
      return dfs(grid,start_x,start_y,cntzero);

    }
};
// 980. Unique Paths III
var uniquePathsIII = function(grid) {
    const M = grid.length; // grid height
    const N = grid[0].length; // grid width
    let result = 0; // final result
    let startY = 0, startX = 0; // starting point coordinates
    let finalY = 0, finalX = 0; // endpoint coordinates
    let empty = 0; // count of empty squares
    let visit = Array(M); // visited squares (MxN of booleans)

    // Initialization of required variables
    for (let i = 0; i < M; i++) {
        visit[i] = Array(N).fill(false); // now: "visit[i][j] === false"
        for (let j = 0; j < N; j++) {
            switch (grid[i][j]) {
                case 0 : empty++; break;
                case 1 : startY = i; startX = j; break;
                case 2 : finalY = i; finalX = j; break;
            }
        }
    }

    // Recursively run DFS and get the answer in the "result" variable
    dfs(startY, startX, visit, 0);
    return result;

    // DFS implementation
    function dfs (startY, startX, visit, step) {

        // If it's a wrong square, then exit immediately
        if (startY < 0 || startY >= M || // off grid (height)
            startX < 0 || startX >= N || // off grid (width)
            visit[startY][startX] || // already processed
            grid [startY][startX] === -1 // this is an obstacle
        ) return; // ... exit now

        // Base case: we're at the endpoint, need to stop the recursion.
        // If all of squares are visited, increase the "result":
        // (count of paths from start to the end).
        if (startY === finalY && startX === finalX) {
            if (step - 1 === empty) result++;
            return;
        }

        // Run DFS for neighboring squares.
        // Increase the number of steps (count of the visited squares).
        visit[startY][startX] = true; // mark current square as visited
        dfs(startY-1, startX, visit, step + 1); // top
        dfs(startY, startX+1, visit, step + 1); // right
        dfs(startY+1, startX, visit, step + 1); // bottom
        dfs(startY, startX-1, visit, step + 1); // left
        visit[startY][startX] = false; // restore visited square
    }
};
Unique Paths III