In Java!!! A rat is located at the top-left corner of a M × N grid A. M 1, N 1.

Question

In Java!!!

A rat is located at the top-left corner of a M × N grid A. M 1, N 1. It can only move either down or right at any point in time. The rat is trying to reach the bottom-right corner of the grid. How many possible unique paths are there? For example, if M = 2, N = 2, there are two possible unique paths: A[0][0] A[0][1] A[1][1], A[0][0] A[1][0] A[1][1].

(a) Based on the recurrence relation, give a naive recursive way to solve this problem

(b) Use dynamic programming to solve this problem

(c) Now consider there are some obstacles in the grid A, the rat can not go through the obstacles. An obstacle and empty space is marked as 1 and 0 respectively. How many unique paths?

Explanation / Answer

Given a grid of size M x N. Rat can move either down or right. Destination cell is M, N. Let's try to find reurrence for number of unique paths.

let us define a 2d array paths[M][N]. paths[i][j] gives number of unique paths to reach the cell M,N. Base case is , if the rat is at the destination i.e M,N. There is only one way. That means paths[M][N] = 1.

So, number of paths from a point i,j is given by

path(i,j) = path(i+1,j)+path(i,j+1). This is our recurrence .i.e number of paths from a point is equal to number of ways from the point below and the point to the right of it.'

The below program finds the solution in naive recursive way

public class MainClass {

  
    public static int paths(int i, int j, int grid[][]){
      
        //If present position is the target, return 1
        if(i==grid.length-1&&j==grid[0].length-1){
            return 1;
        }
      
        //If position of the rat is outside the grid, return 0
        if(i>=grid.length||j>=grid[0].length){
            return 0;
        }
      
        //return sum of paths of below and the right cell
        return paths(i+1,j,grid)+paths(i,j+1,grid);
    }
    public static void main(String[] args){
        System.out.println(paths(0,0,new int[2][4]));
    }
}

b. Dynamic programming method

public class MainClass {

     
    public static int paths(int i, int j, int grid[][], int dp[][]){
      
        //If position of the rat is outside the grid, return 0
        if(i>=grid.length||j>=grid[0].length){
            return 0;
        }
      
        //If number of paths for the position i,j is already calculated, use it instead of finding it agin
        if(dp[i][j]!=-1){
            return dp[i][j];
        }
      
        //return sum of paths of below and the right cell. store the result in dp table
        dp[i][j] = paths(i+1,j,grid,dp)+paths(i,j+1,grid,dp);
        return dp[i][j];
    }
    public static void main(String[] args){
        int M=13,N=7;
        int dp[][] = new int[M][N];
        for(int i=0;i<M;i++){
            Arrays.fill(dp[i], -1);
        }
        dp[M-1][N-1] = 1;
        int grid[][] = new int[M][N];
        System.out.println(paths(0,0,grid,dp));
    }
}

c. Dynamic programming solution with obstacles in the grid

import java.util.Arrays;

public class MainClass {

     
    public static int paths(int i, int j, int grid[][], int dp[][]){     
      
      
        //If position of the rat is outside the grid, return 0
        if(i>=grid.length||j>=grid[0].length){
            return 0;
        }
      
        //If number of paths for the position i,j is already calculated, use it instead of finding it agin
        if(dp[i][j]!=-1){
            return dp[i][j];
        }
      
        //There is an obstacle at i,j
        if(grid[i][j]==1){
            dp[i][j] = 0;
            return 0;
        }
      
        //return sum of paths of below and the right cell. store the result in dp table
        dp[i][j] = paths(i+1,j,grid,dp)+paths(i,j+1,grid,dp);
        return dp[i][j];
    }
    public static void main(String[] args){
        int M=2,N=7;
        int dp[][] = new int[M][N];
        for(int i=0;i<M;i++){
            Arrays.fill(dp[i], -1);
        }
        dp[M-1][N-1] = 1;
        int grid[][] = new int[M][N];
        grid[1][0] = 1;
        System.out.println(paths(0,0,grid,dp));
    }
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.