Last Updated: 4 Mar, 2021

Underground Explorer

Moderate

Asked in company

Solve now

Problem statement

You are given a N*M 2-D array grid, which represents an underground sewage system where N is the height of the sewage system, and M is the width. There are pipelines in the sewage system, and in total, there are seven types of pipes, as shown below:

Type - 1

altImage

Type - 2

altImage

Type - 3

altImage

Type - 4

altImage

Type - 5

altImage

Type - 6

altImage

Type - 7

altImage

The given N*M grid will contain numbers from 0-7, where 0 will mean that there is no pipeline, and numbers from 1 to 7 will indicate the type of pipeline present at that point.

Now you are standing at any given point (X, Y) in this sewage system, and you can walk up to L units in any direction of your choice from the starting point. Your task is to calculate the total number of pipes you can explore if you start from your initial position.

Note:

1. The given input will always contain numbers from 0 to 7.
2. The point where you are initially standing will always be a valid point. I.e., you will always be present inside the N*M grid.

Input Format:

The first line contains an integer T, which denotes the number of test cases or queries to be run. Then, the T test cases follow.

The first line of each test case contains five integers N, M, X, Y, and L, as described in the problem statement.

Then each of the next N lines will contain M integers, each from 0-7, describing the sewage system.

Output Format:

For each test case, print in a new line, one integer representing the total number of pipes you can explore if you start from your initial position.

Output for each test case will be printed in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 100
1 <= N, M <= 1000
0 <= X < N
0 <= Y < M
1 <= L <= 10^6

Time Limit: 1 second

Solve now

Approaches

01 Approach

Here we will be using the BFS approach. Initially, we are standing at a given point (X, Y), and from this point, we will explore in all four directions if the pipelines allow us to visit(i.e., If they are connected) and if we have distance left to cover. So initially we will push the current position and the length we can travel further in a queue. Then we check in all four directions. If the pipe is not visited before and if we can go in any direction with a positive distance left, then we will push that point and the distance left in the queue and will repeat this process till the queue is not empty. Each time we visit an unvisited point whose value is greater than 0, we will increase the answer count and finally return the answer.

Steps:

Create a 2-D visited array (say vis) that will tell if we have visited any point before or not and a queue (say q) that will store the position and the length left to travel. Initialize all the elements of the vis array to false.
Create a function isValid(x, y, N, M) that returns true if the coordinate (x, y) is a valid coordinate in the N*M grid, or else it will return false.
- bool isValid(x, y, N, M):
  - If x >=0 and x < N and y >= 0 and y < M, return true.
  - Or else return false.
Create 4 functions namely connectUp(x, y, grid), connectDown(x, y, grid), connectLeft(x, y, grid) and connectRight(x, y, grid) that returns true if the current pipe connects with the respective direction or else it return false.
- connectUp(x, y, grid):
  - If grid[x][y] is 1 or 2 or 4 or 7, then return true.
  - Else return false.
- connectDown(x, y, grid):
  - If grid[x][y] is 1 or 2 or 5 or 6, then return true.
  - Else return false.
- connectLeft(x, y, grid):
  - If grid[x][y] is 1 or 3 or 6 or 7, then return true.
  - Else return false.
- connectRight(x, y, grid):
  - If grid[x][y] is 1 or 3 or 4 or 5, then return true.
  - Else return false.
Create a variable ans initialized it with 0 that will store the answer.
Create a queue (say q) for the BFS to store the current point and the distance left to travel.
Add initial point (X,Y) and the distance L to q. i.e. q.add({X,Y,L}) and mark vis[x][y] as true.
Run a while loop till q is not empty and do:
- Take the first node of the queue in curr variable and pop the first element.
- Increment the ans variable by 1. i.e. ans = ans + 1.
- If curr.distanceRemaining > 1:
  - If isValid(curr.X-1, curr.Y, N, M) and connectUp(curr.X, curr.Y, grid) is true and connectDown(curr.X-1, curr.Y, grid) is true and vis[curr.X-1][curr.Y] is false:
    - Add (curr.X-1, curr.Y, curr.distanceRemaining-1) to q.
    - Mark vis[curr.X-1][curr.Y] as true.
  - If isValid(curr.X+1, curr.Y, N, M) and connectDown(curr.X, curr.Y, grid) is true and connectUp(curr.X+1, curr.Y, grid) is true and vis[curr.X+1][curr.Y] is false:
    - Add (curr.X+1, curr.Y, curr.distanceRemaining-1) to q.
    - Mark vis[curr.X+1][curr.Y] as true.
  - If isValid(curr.X, curr.Y+1, N, M) and connectLeft(curr.X, curr.Y+1, grid) is true and connectRight(curr.X, curr.Y, grid) is true and vis[curr.X][curr.Y+1] is false:
    - Add (curr.X, curr.Y+1, curr.distanceRemaining-1) to q.
    - Mark vis[curr.X][curr.Y+1] as true.
  - If isValid(curr.X, curr.Y-1, N, M) and connectLeft(curr.X, curr.Y, grid) is true and connectRight(curr.X, curr.Y-1, grid) is true and vis[curr.X][curr.Y-1] is false:
    - Add (curr.X,curr.Y-1,curr.distanceRemaining-1) to q.
    - Mark vis[curr.X][curr.Y-1] as true.
Finally, return the ans variable as the answer.

Solve now