PROBLEM LINK:
Author: Rishabh Gupta
Tester: Priyanshu Jain
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Matrix, Flood-Fill Algorithm.
PROBLEM:
Given a NxM matrix containing paths and walls, a player with starting co-ordinates, exit point co-ordinates, and
the co-ordinates of starting point of the flood. Check if player or the water reaches first at the exit point.
QUICK EXPLANATION:
Apply flood-fill algorithm from both player and water with the modification of adding a counter to count the number
of steps taken to reach the exit point.
EXPLANATION:
We will apply a modified version of flood-fill algorithm.
A good tutorial on flood-fill can be found [here](https://www.hackerearth.com/practice/algorithms/graphs/flood-fill- algorithm/tutorial/). And the Wikipedia link is here.
We will apply our flood-fill something like this:
bool flood(int i, int j, int dest_i, int dest_j)
{
if(mat[i][j] == -1) // a wall
return false;
if(i == dest_i && j == dest_j)
return true;
return flood(i+1, j, dest_i, dest_j) || flood(i-1, j, dest_i, dest_j) || flood(i, j+1, dest_i, dest_j) || flood(i, j-1,
dest_i, dest_j);
}
This code only checks if the point (dest_i, dest_j) is reachable or not.
Notice that there is no boundary condition, i.e. checking if we reached any edge or corner of the matrix. For this
we will be surrounding our matrix with wall. And take the size of matrix as (N+2)x(M+2), for accommodating the
walls at the edges.
For example, if our matrix input was:
0 0 X 0
0 0 X 0
0 X X X
0 0 0 X
We will save it as:
X X X X X X surrounding walls
X 0 0 X 0 X
X 0 0 X 0 X
X 0 X X X X
X 0 0 0 X X
X X X X X X
This will also ensure 1-based indexing.
Now, we will modify it by adding a counter on every call.
void flood(int i, int j, int dest_i, int dest_j, int cnt)
{
if(mat[i][j] == -1) //a wall
{ //do nothing
return;
}
if(matrix[i][j] == 0 || matrix[i][j] > cnt)
{
matrix[i][j] = cnt;
if(i == dest_i && j == dest_j)
{
return;
//no need to flood more
}
else
{
cnt++;
flood(i+1, j, dest_i, dest_j, cnt);
flood(i-1, j, dest_i, dest_j, cnt);
flood(i, j+1, dest_i, dest_j, cnt)
flood(i, j-1, dest_i, dest_j, cnt);;
}
}
}
We will flood the matrix two times, once for water, and once for the player. This will give us the shortest distance
it will take for both water and player to reach the exit point. Comparing these values will give us the answer.
For more clarity and the implementation see the solution given below.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.