Unique Paths III

On a 2-dimensional grid, there are 4 types of squares.

1 represents the starting square.  There is exactly one starting square.

2 represents the ending square.  There is exactly one ending square.

0 that represents empty squares we can walk over.

-1 represents obstacles that we cannot walk over.

Example:

Input:  grid[][]={{1,0,0,0},{0,0,0,0},{0,0,2,-1}}
Output: 2

Approach

Java

public class UniquePathsIII {
    // variable to hold the final answer
    static int res;

    public static void main(String[] args) {
        int obstacleGrid[][] = { { 1, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 2, -1 } };
        res = 0;
        int paths = uniquePaths(obstacleGrid);
        System.out.println(paths);
    }

    static void dfs(int i, int j, int n, int m, int[][] grid, int x, int cnt) {
        // if the cell is not in the boundary
        if (i < 0 || i >= n || j < 0 || j >= m || grid[i][j] == -1)
            return;

        // if we reach to the final position
        if (grid[i][j] == 2) {
            if (x + 1 == cnt)
                res++;
            return;
        }
        grid[i][j] = -1;

        // call for down
        dfs(i + 1, j, n, m, grid, x, cnt + 1);

        // call for up
        dfs(i - 1, j, n, m, grid, x, cnt + 1);

        // call for right
        dfs(i, j + 1, n, m, grid, x, cnt + 1);

        // call for left
        dfs(i, j - 1, n, m, grid, x, cnt + 1);
        grid[i][j] = 0;

    }

    // function to find all unique
    // paths from given starting position
    // to the given end position
    static int uniquePaths(int[][] grid) {
        int n = grid.length;
        // empty grid
        if (n == 0)
            return 0;
        int m = grid[0].length;
        int row = 0, col = 0, x = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    row = i;
                    col = j;
                }

                // count of empty squre
                if (grid[i][j] == 0)
                    x++;
            }
        }

        // call dfs for the start position and count of
        // number of empty cell
        dfs(row, col, n, m, grid, x, 0);
        return res;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;

//varible to hold the final
//answer
int res=0;
void dfs(int i,int j,int n,int m,vector<vector<int>>&grid,
        int x,int cnt)
{
        //if the cell is not in the boudary
        if(i<0||i>=n||j<0||j>=m||grid[i][j]==-1)
               return;

        //if we reach to the final position
      if(grid[i][j]==2)
        {
            if(x+1==cnt)
                  res++;
            return;
        }
        grid[i][j]=-1;

        //call for down 
        dfs(i+1,j,n,m,grid,x,cnt+1);

        //call for up
        dfs(i-1,j,n,m,grid,x,cnt+1);
        
        //call for right
        dfs(i,j+1,n,m,grid,x,cnt+1);

        //call for left
        dfs(i,j-1,n,m,grid,x,cnt+1);
         grid[i][j]=0;
    
}

//function to find all unique
//paths from given starting position
//to the given end position
int uniquePaths(vector<vector<int>>& grid) 
{
    int n=grid.size();
   //empty grid
   if(n==0)
          return 0;
    int m=grid[0].size();
    int row,col,x=0;


     for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(grid[i][j]==1)
                {
                    row=i;
                    col=j;
                }

              //count of empty squre
                if(grid[i][j]==0)
                       x++;
            }
        }

    //call dfs for the start position and count of
    //number of empty cell
        dfs(row,col,n,m,grid,x,0);
        return res;
}

int main()
{
    vector<vector<int>> grid={{1,0,0,0},
                             {0,0,0,0},
                            {0,0,2,-1}};
    int paths=uniquePaths(grid);
    cout<<paths<<"\n";
    return 0;
}