typedef vector<bool> vb;
typedef vector<int> vi;
class Solution {
public:
    int uniquePathsIII(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        int nodes = n*m;
        //nodes are numbered from 0.....m-1 m.....2m-1 2*m.....
        //build adjoint list
        int pos1, pos2;
        for(int i = 0; i<n; i++) for(int j = 0; j<m; j++){
        	if(grid[i][j]==1) pos1 = i*m + j;
        	if(grid[i][j]==2) pos2 = i*m + j;
        }

        vi adj[nodes];
        vector<pair<int, int> > neighbours = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
        
        int target = 0;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(grid[i][j]==-1) continue;
                int src = i*m + j;
                target |= (1<<src);
                if(src==pos1) continue;
                for(auto &p: neighbours){
                    int x = p.first + i, y = p.second + j;
                    int dest = x*m + y;
                    if(dest==pos2) continue;
                    if(x>=0&&x<n&&y>=0&&y<m&&grid[x][y]!=-1)
                        adj[src].push_back(dest);
                }
            }
        }
        
        vector<vi> dp(1<<nodes, vi(nodes, 0));
        for(int i = 0; i<nodes; i++)
            dp[1<<i][i] = 1;

        for(int i = 0; i < (1<<nodes); i++){
        	for(int j = 0; j < nodes; j++){
            	if(i&(1<<j)){
                	for(auto &k:adj[j]){
                    	if(i&(1<<k))
                        	dp[i][j] += dp[i^(1<<j)][k];
                	}
            	}	
        	}
        }
        return dp[target][pos2];
    }
};