Underground Explorer

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:

1. 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.
2. 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.
3. 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.
4. Create a variable ans initialized it with 0 that will store the answer.
5. Create a queue (say q) for the BFS to store the current point and the distance left to travel.
6. 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.
7. 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.
8. Finally, return the ans variable as the answer.

O(N*M), Where N is the height of the sewage system, and M is the width.

Since we are doing a BFS on the given grid, we will visit each node only once. Hence, the time complexity will be O(N*M).

O(N*M), Where N is the height of the sewage system, and M is the width.

Since we have created a visited array of size N*M and also our queue will store the coordinates of the grid. Hence, the space complexity will be O(N*M).