<p>You are given an <code>m x n</code> integer array <code>grid</code> where <code>grid[i][j]</code> could be:</p>

<ul>
	<li><code>1</code> representing the starting square. There is exactly one starting square.</li>
	<li><code>2</code> representing the ending square. There is exactly one ending square.</li>
	<li><code>0</code> representing empty squares we can walk over.</li>
	<li><code>-1</code> representing obstacles that we cannot walk over.</li>
</ul>

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/02/lc-unique1.jpg" style="width: 324px; height: 245px;" />
<pre>
<strong>Input:</strong> grid = [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> 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)
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/02/lc-unique2.jpg" style="width: 324px; height: 245px;" />
<pre>
<strong>Input:</strong> grid = [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> 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)
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/08/02/lc-unique3-.jpg" style="width: 164px; height: 165px;" />
<pre>
<strong>Input:</strong> grid = [[0,1],[2,0]]
<strong>Output:</strong> 0
<strong>Explanation:</strong> 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.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

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

class Solution {
public:
    int uniquePathsIII(vector<vector<int>>& grid) {
        int pathCount=0;
        //set<set<int>> paths;
        int max_size=0;

        //store ind using (row+1*100) +col
        int start_ind;
        int stop_ind;
        set<int> obstacles;

        //find start  and end square and obstacles
        for(int i=0; i<grid.size();i++){
             for(int j=0; j<grid[i].size();j++){
                if(grid[i][j]==1) {
                    start_ind=((i)*100) + j;
                }

                else if(grid[i][j]==2) {
                    stop_ind=((i)*100) +j;
                }

                else if(grid[i][j]==-1){
                    obstacles.insert(((i)*100) +j);
                }

                else {
                    //this is an empty square
                    max_size++;
                }
             }
        }

        //edge case if the box only has start and end square
        if(max_size==0) {
            //start and end square are adjacent
            if(( abs(start_ind-stop_ind)==100) || abs(start_ind-stop_ind)==1) {
                return 1;
            }
            //there are no paths available
            return 0;
        }

        //find all unique paths
        set<int> curr_path {start_ind};
        pair<int,int> max_inds=make_pair(grid.size(),grid[0].size());
        return FindPath(curr_path,max_size,max_inds,start_ind,stop_ind,obstacles);

    }

    int FindPath( set<int>& curr_path,int max_size,pair<int,int> max_inds,int start_ind,int stop_ind,set<int>& obstacles){
        cout<<start_ind;
        cout<<"\n";
        cout<<curr_path.size();
        int paths=0;
        if( start_ind==stop_ind ){
            //complete path found
            cout<<"stop";
            if(curr_path.size()==max_size+2){
                cout<<"path found";
                paths++;
                for(int path: curr_path){
                    cout<<path;
                }
            }
            curr_path.erase(curr_path.find(start_ind));
            //exit early if stop square is reached before all squares traversed
            return paths;
        }


        //check for all valid moves: up,down, left,right
        //move up
        if( start_ind>=100 && obstacles.find(start_ind-100) == obstacles.end() && curr_path.find(start_ind-100) == curr_path.end()) {
            curr_path.insert(start_ind-100);
            paths+=FindPath(curr_path,max_size,max_inds,start_ind-100,stop_ind,obstacles);
        }

        //move down
        if( ((int)((start_ind+100)/100))< max_inds.first && obstacles.find(start_ind+100) == obstacles.end() && curr_path.find(start_ind+100) == curr_path.end()) {
            curr_path.insert(start_ind+100);
            paths+=FindPath(curr_path,max_size,max_inds,start_ind+100,stop_ind,obstacles);
        }

        //move left: index after subtracting one should have the same first digit if it not the first column
        if( start_ind>0 && ((int)((start_ind)/100)) ==((int)((start_ind-1)/100)) && obstacles.find(start_ind-1) == obstacles.end() && curr_path.find(start_ind-1) == curr_path.end()) {
            curr_path.insert(start_ind-1);
            paths+=FindPath(curr_path,max_size,max_inds,start_ind-1,stop_ind,obstacles);
        }

        //move right
        if( (( (int)((start_ind+1)%100))< max_inds.second) && (obstacles.find(start_ind+1) == obstacles.end()) && (curr_path.find(start_ind+1) == curr_path.end())) {
            curr_path.insert(start_ind+1);
            paths+=FindPath(curr_path,max_size,max_inds,start_ind+1,stop_ind,obstacles);
        }

        //curr_path={};
        curr_path.erase(curr_path.find(start_ind));
        return paths;
    }
};
20518