Last Updated: 4 Sep, 2022

NINJA AND THE GRID

Moderate

Asked in company

Solve now

Problem statement

There is a N X N ‘GRID’ in which some cells are empty while others are blocked. Empty cells are denoted by ‘.’ and blocked cells by ‘#’. Initially, the ninja is standing at the bottom of the GRID.

Ninja can start at any one of the bottom empty cells. He can take steps either up or right, i.e., from the cell ( i, j ) to cell ( i - 1, j ) or ( i, j + 1 ). The ninja can not move outside the grid. Once he has taken a step towards right then, he cannot take steps in any other direction.

You need to calculate the number of ways he can reach the right end of the grid.

Note: Ninja can not pass through the blocked cells.

Example:

Input:

‘N’ = 3
‘GRID’ = [ # . .  ] [ # . . ] [ # . . ]

Following are the possible ways:

( 2, 1 ) => ( 2, 2 )
( 2, 1 ) => ( 1, 1 ) => ( 1, 2 )
( 2, 1 ) => ( 1, 1 ) => ( 0, 1 ) => ( 0, 2 )
( 2, 2 )
( 2, 2 ) => ( 1, 2 )
( 2, 2 ) => ( 1, 2 ) => ( 0, 2 )

Where ( i, j ) denotes the cell GRID [ i ] [ j ].

Input Format:

The first line contains ‘T,’ denoting the number of test cases.

The first line of each test case contains ‘N’ denoting the dimensions of the ‘GRID’.

Each of the next ‘N’ lines contains ‘N’ characters denoting the cells of the ‘GRID’.

Output Format:

Return the number of ways he can reach the right end of the ‘GRID’.

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10    
1 <= N <= 1000

Time Limit: 1 sec

Solve now

Approaches

01 Approach

If any grid cell does not have a blocked cell in its right and down directions, then a path is always possible from the bottom to that cell and from the cell to the right end of the ‘GRID’. So, the total number of ways to reach the right end is the number of such cells.

For all the cells of the GRID, we can find out if their right and down directions have no blocked cells.

For each cell, we can traverse the right and bottom directions. If no blocked element is found, a path exists through the cell.

The steps are as follows:-

function countCells ( int N , [ char ] [ char ] GRID ):

Initialise a variable ‘ANS’ = 0
Run a loop from ‘i’ =0 to ‘N’ -1:
- Run a loop from ‘j’ =0 to ‘N’ -1:
  - Initialise a variable ‘IsCellPossible’ = true
    - Run a loop from ‘k’ = ‘j’ to ‘N’ -1:
      - If ( GRID [ i ] [ k ] == ‘#’ ) ‘IsCellPossible’ = false
    - Run a loop from ‘k’ = ‘i’ to ‘N’ -1:
      - If ( GRID [ k ] [ j ] ==’ #’ ) ‘IsCellPossible’ = false
  - If ( IsCellPossible ) ‘ANS’ = ‘ANS’ + 1
Return ‘ANS’

Solve now

02 Approach

We can use precomputation here. We will build a boolean matrix of size ‘N’ X ‘N’ ‘canGoRight’ where

canGoRight [ i ] [ j ] denotes that the cell GRID [ i ] [ j ] has no blocked element in the right direction.

To determine the ‘canGoRight’ we can traverse the row from top to bottom and the column from right to left. Initially, all cells have their ‘canGoRight’ as false. While traversing, we set canGoRight of the cell as true. If we get a blocked cell, we move to the next row. The cells we did not encounter while traversing have their ‘canGoRight’ as false.

To find the cells which have no blocked cells in their right and down directions, We can traverse columns from left to right and rows from bottom to top. If we find a blocked cell, we move to the next column.

While traversing, if ‘canGoRight’ of the current cell is true, then the ninja can reach the right end of the ‘GRID’, and we increment an ‘ANS’ variable by one.

The steps are as follows:

function ( int N, [ char ] [ char ] GRID ):

Initialise a boolean matrix ‘canGoRight’ of size ‘N’ X ‘N’ with false.
Run a loop from ‘i’ = 0 to ‘N’ - 1:
- Run a loop from ‘j’ = ‘N’ - 1 to 0:
  - If ( GRID [ i ] [ j ] == ’#’ ):
    - Break
  - canGoRight [ i ] [ j ] = true
Initialise a variable ‘ANS’ = 0.
Run a loop from ‘j’ = 0 to ‘N’ - 1:
- Run a loop ‘i’ = ‘N’ - 1 to 0:
  - If ( GRID [ i ] [ j ] == ’#’ ):
    - Break.
  - If ( canGoRight [ i ] [ j ] == true ):
    - ‘ANS’ = ‘ANS’ + 1.
Return ‘ANS’.

Solve now