980

class Solution {
int ans=0;
int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, 1, -1, 0};

public:
    int uniquePathsIII(vector<vector<int>>& grid) {
        int startx, starty, count=0;
        for(int i=0; i<grid.size(); i++)
            for(int j=0; j<grid[i].size(); j++){
                if(grid[i][j] == 1)
                    startx = i, starty = j;
                if(grid[i][j] != -1)
                    count++;
            }
        dfs(startx, starty, grid, count-1);
        return ans;
    }

    void dfs(int x, int y, vector<vector<int>> &grid, int count){
        if(x<0 || y<0 || x>=grid.size() || y>=grid[x].size() || grid[x][y]==-1) return;
        if(!count && grid[x][y] == 2){
            ans++;
            return;
        }
        else{
            int tmp = grid[x][y];
            grid[x][y] = -1;
            for(int i=0; i<4; i++)
                dfs(x+dx[i], y+dy[i], grid, count-1);
            grid[x][y] = tmp;
        }
    }
};