SRTX16D - Editorials

PROBLEM LINK:

Practice

Contest

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.

//