NINJA AND THE GRID

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
1 upvote
Asked in company
Samsung

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 ].
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
2
3
#.#
#..
#.#
3
###
.#.
.#.

Sample Output 1:

1
2
Explanation Of Sample Input 1:
For the first test case:-
The only possible path is:
( 2, 1 ) => ( 1, 1 ) => ( 1, 2 )

For the second test case:-
Following are the possible ways:
( 2, 2 ) => ( 2, 1 )
( 2, 2 )
Sample Input 2:
2
3
#..
#..
#.#
2
..
..
Sample Output 2:
2
4
Hint

 Try to find the cells whose right and down directions have no blocked cells.

Approaches (2)
Brute Force

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 ):

  1. Initialise a variable ‘ANS’ = 0
  2. 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
  3. Return ‘ANS’
Time Complexity

O (  N3  ), Where ‘N’ is the dimension of ‘GRID’.

 

For each GRID cell ( total N2  cells), we are traversing a maximum of ‘N’ steps downward and ‘N’ steps rightward, so, at most, N2  * 2 *N steps which are equivalent to O ( N3  ).

 

Hence, the time complexity is O (  N3  ).

Space Complexity

O ( 1 )

 

We have no extra auxiliary space. A constant amount of space is being used.

 

Hence, the space complexity is O ( 1 ).

Code Solution
(100% EXP penalty)
NINJA AND THE GRID
Full screen
Console