BUG2K16C - Editorial

PROBLEM LINK:

Contest

Author: Rishabh Karnad

Tester: Omkar Prabhu

Editorialist: Rishabh Karnad

DIFFICULTY:

Easy

PRE-REQUISITES:

[Dynamic Programming][2]

PROBLEM:

Given a rectangular grid of dimensions m x n, in which each cell consists of either a 1 or a 0, find out whether there exists a path from (m,0) to (0,n) which only passes through cells containing 1s, while only making the following moves:

  1. (i,j) -> (i-1,j) [An UP or NORTH move]
  2. (i,j) -> (i,j+1) [A RIGHT or EAST move]

SOLUTION:

This problem has a typical dynamic programming solution.

The grid itself is represented as a matrix, say grid[m][n], whose contents are 0s and 1s and taken as input. A second matrix, say path_exists[m][n] is used to contain the information about the existence of a path to every cell; if path_exists[i][j] is 1, then there is a path from (m,0) to (i,j) and if it is 0, there is no path to (i,j).

The algorithm begins at (m,0) and may proceed row-by-row, column-by-column or diagonal-wise. For simplicity, we consider a row-by-row approach. Two loops are required: an inner j loop for columns and an outer i loop for rows. For each cell (i,j), we check if:

  1. Either or both path_exists[i+1][j] and path_exists[i][j-1] is 1. If yes, it means a path exists to one of those cells (i+1,j) or (i,j-1).
  2. grid[i][j] is 1, meaning that a path can pass through it.

If both conditions are satisfied, then the path to (i+1,j) or (i,j-1) can be extended to (i,j). Hence a path to (i,j) exists and we mark path_exists[i][j] as 1. Otherwise, we mark it 0.

When the algorithm terminates, the value of path_exists[0][n] will indicate the existence of a path between (m,0) and (0,n).

TIME COMPLEXITY:

Since each cell must be checked and operation on each cell takes constant time, time complexity is O(n^2).

SPACE COMPLEXITY:

O(n^2)

It can be reduced to O(n) by keeping track of only two rows at a time in path_exists and the algorithm can still be made to work correctly.

AUTHOR’S SOLUTION

Will be provided soon.