We are given m*n matrix which can have a number between 0 and 7. Each number represents a pipe with a shape as follows:
Two pipes are considered connected if their end points connect.
Example:
If matrix is as follows:
0040
1360
5000Pipe 1 and 3{1 opens to right. 3 opens to left} are connected. Other connected pipes are 3 and 6(3 opens to right. 6 opens to left).
4 and 6 are not connected as 6 does not open to top, and 4 does not open to bottom.
1 and 5 are also not connected as even though 1 opens to bottom, 5 is not open to top.
Given this matrix, start point (X, Y) and length of probe tool “L”, find out how many pipes{matrix elements} can be reached.
Note: Probe tool: is a measuring tool, if 6 pipes can be reached but length of probe tool is 4. Answer will be 4 if 3 pipes can be reached but length of probe tool is 4. Answer will be 3.
Example:
Starting index: (1, 0) , Length of probe: 4
Matrix:
{0040
1360
5000}connected pipes via probe- (1, 0)->(1, 1)->(1, 2)
Ans- 3Starting index: (0, 0) , Length of probe: 4
Matrix:
{0040
1360
5000}
connected pipes via probe- 0
Ans- 0Starting index: (1, 0) , Length of probe: 2
Matrix:
{0040
1360
5000 }
connected pipes via probe- (1, 0)->(1, 1)
Ans- 2
Key Steps to solve:
Find which of the neighboring pipe elements can be accessed from one starting point {Maintaining exhaustive list of checks to ascertain neighboring criteria as defined above}.
Find a method to process through the elements to find the next set of elements which can be accessed. {Traversing through the graph}. It should be noted that we wish to reach all nodes which are accessible from start node with distance less than “L”. The focus is not on reaching lot of nodes, but on reaching them with lesser moves from start point (X, Y).
Recursion:
We mark all the nodes as unvisited and visited node count as 0. If a node marked as unvisited is processed during recursion, increment visited node count by 1 and mark it as visited.
We start by visiting Start node (X, Y) and then recursively visiting all its connected neighbors (based on checks for connected criteria as defined above) till the recursion depth of “L”.
Drawback:
In case of highly connected matrix (almost all pipes are connected together and multiple ways to reach a pipe exists), we reach a node multiple times and process it multiple times which may lead to high running time. We can optimize it by checking that we process a node again only if we have reached it with a lower recursion level.
This is not a DFS solution because we reprocess a node, even if already visited, as it is possible that the new visit may update the visiting depth of the node to lower level and greater depth be reached after this node.
Breadth-First Search:
We mark all the nodes as unvisited and visited node count as 0. If a node marked as unvisited is processed during processing, increment visited node count by 1.
We start by pushing the start node (X, Y) into a queue with depth 1 and then start processing the queue till it is empty.
In each iteration a member of queue is taken out and its connected neighbors are analyzed. If neighbors are unvisited and depth of current element is not greater than L, connected elements are put into queue, marked visited and visited node count increased by 1.
As BFS performs level order traversal of nodes, it is not possible that a visited node be reached in a smaller distance. So, drawback of previous method cannot exist. This is the optimal solution for this problem.
Simplification possible in the solutions for easy coding:
Since there are 7 types of pipes, we will have to put multiple if conditions leading to nested if statements which are difficult to debug. It can be simplified by converting the 7 values into direction based data. For e.g. each value can be transformed into a structure with 4 Boolean variables, one for each direction. Alternatively, each number can be mapped to a 4 bit number where each bit represents a direction. After this input reduction, checks will become simpler and with less complexity.
Implementation:
C++
#include <bits/stdc++.h>using namespace std;#define Max 1000#define row_size 3#define col_size 4int x = 1, y = 0; // starting index(x, y),int l = 4; // length of probe tool// input matrix containing the pipesint mt[row_size][col_size] = { { 0, 0, 4, 0 }, { 1, 3, 6, 0 }, { 5, 0, 0, 0 } };// visited matrix checks for cells already visitedint vi[row_size][col_size]; // calculates the depth of connection for each cellint depth[row_size][col_size]; int f = 0;int r = 0;// queue for BFSstruct node { int x; int y; int d;};node q[Max];void push(int a, int b, int d) // push function{ node temp; temp.x = a; temp.y = b; temp.d = d; q[r++] = temp; vi[a][b] = 1;}node pop() // pop function{ node temp; temp.x = q[f].x; temp.y = q[f].y; temp.d = q[f].d; f++; return temp;}// It can be simplified by converting the 7// values into direction based data. For e.g. // each value can be transformed into a structure// with 4 Boolean variables, one for each direction. // Alternatively, each number can be mapped to a 4// bit number where each bit represents a direction.bool s1(int i, int j) // conversion to final direction{ if (i >= 0 && i < row_size && j >= 0 && j < col_size && vi[i][j] == 0 && (mt[i][j] == 1 || mt[i][j] == 3 || mt[i][j] == 6 || mt[i][j] == 7)) return true; else return false;}bool s2(int i, int j) // conversion to final direction{ if (i >= 0 && i < row_size && j >= 0 && j < col_size && vi[i][j] == 0 && (mt[i][j] == 1 || mt[i][j] == 2 || mt[i][j] == 4 || mt[i][j] == 7)) return true; else return false;}bool s3(int i, int j) // conversion to final direction{ if (i >= 0 && i < row_size && j >= 0 && j < col_size && vi[i][j] == 0 && (mt[i][j] == 1 || mt[i][j] == 3 || mt[i][j] == 4 || mt[i][j] == 5)) return true; else return false;}bool s4(int i, int j) // conversion to final direction{ if (i >= 0 && i < row_size && j >= 0 && j < col_size && vi[i][j] == 0 && (mt[i][j] == 1 || mt[i][j] == 2 || mt[i][j] == 6 || mt[i][j] == 5)) return true; else return false;}// search for connection// We start by pushing the start node (X, Y) into a queue// with depth 1 and then start processing the queue till // it is empty.void bfs(int x, int y, int d) { push(x, y, d); while (r > f) { node temp = pop(); int i = temp.x; int j = temp.y; int c = temp.d; depth[i][j] = c; if (mt[i][j] == 1 || mt[i][j] == 3 || mt[i][j] == 4 || mt[i][j] == 5) { if (s1(i, j + 1)) push(i, j + 1, c + 1); } if (mt[i][j] == 1 || mt[i][j] == 2 || mt[i][j] == 6 || mt[i][j] == 5) { if (s2(i + 1, j)) push(i + 1, j, c + 1); } if (mt[i][j] == 1 || mt[i][j] == 3 || mt[i][j] == 7 || mt[i][j] == 6) { if (s3(i, j - 1)) push(i, j - 1, c + 1); } if (mt[i][j] == 1 || mt[i][j] == 2 || mt[i][j] == 4 || mt[i][j] == 7) { if (s4(i - 1, j)) push(i - 1, j, c + 1); } }}int main() // main function{ f = 0; r = 0; // matrix for (int i = 0; i < row_size; i++) { for (int j = 0; j < col_size; j++) { // visited matrix for BFS set to // unvisited for every cell vi[i][j] = 0; // depth set to max initial value depth[i][j] = Max; } } if (mt[x][y] != 0) // condition for BFS bfs(x, y, 1); int nc = 0; for (int i = 0; i < row_size; i++) { for (int j = 0; j < col_size; j++) { if (depth[i][j] <= l) { cout << "(" << i << ", " << j << ")"; nc++; } } } cout << " " << nc << "\n";} |
Python3
Max=1000row_size=3col_size=4x = 1; y = 0 # starting index(x, y),l = 4 # length of probe tool# input matrix containing the pipesmt = [[ 0, 0, 4, 0 ,], [ 1, 3, 6, 0], [ 5, 0, 0, 0],]# visited matrix checks for cells already visitedvi=[[False for _ in range(col_size)]for _ in range(row_size)] # calculates the depth of connection for each celldepth=[[0 for _ in range(col_size)] for _ in range(row_size)] f = 0r = 0# queue for BFSclass node: def __init__(self,x,y,d): self.x=x self.y=y self.d=dq=[None for _ in range(Max)]def push(a, b, d): # push function global r temp=node(a,b,d) q[r] = temp r+=1 vi[a][b] = 1def pop(): # pop function global f temp=node(q[f].x,q[f].y,q[f].d) f+=1 return temp# It can be simplified by converting the 7# values into direction based data. For e.g. # each value can be transformed into a structure# with 4 Boolean variables, one for each direction. # Alternatively, each number can be mapped to a 4# bit number where each bit represents a direction.def s1(i, j): # conversion to final direction if (i >= 0 and i < row_size and j >= 0 and j < col_size and vi[i][j] == 0 and (mt[i][j] == 1 or mt[i][j] == 3 or mt[i][j] == 6 or mt[i][j] == 7)): return True else: return Falsedef s2(i, j): # conversion to final direction if (i >= 0 and i < row_size and j >= 0 and j < col_size and vi[i][j] == 0 and (mt[i][j] == 1 or mt[i][j] == 2 or mt[i][j] == 4 or mt[i][j] == 7)): return True else: return Falsedef s3(i, j): # conversion to final direction if (i >= 0 and i < row_size and j >= 0 and j < col_size and vi[i][j] == 0 and (mt[i][j] == 1 or mt[i][j] == 3 or mt[i][j] == 4 or mt[i][j] == 5)): return True else: return Falsedef s4(i, j): # conversion to final direction if (i >= 0 and i < row_size and j >= 0 and j < col_size and vi[i][j] == 0 and (mt[i][j] == 1 or mt[i][j] == 2 or mt[i][j] == 6 or mt[i][j] == 5)): return True else: return False# search for connection# We start by pushing the start node (X, Y) into a queue# with depth 1 and then start processing the queue till # it is empty.def bfs(x, y, d): push(x, y, d) while (r > f) : temp = pop() i = temp.x j = temp.y c = temp.d depth[i][j] = c if (mt[i][j] == 1 or mt[i][j] == 3 or mt[i][j] == 4 or mt[i][j] == 5) : if (s1(i, j + 1)): push(i, j + 1, c + 1) if (mt[i][j] == 1 or mt[i][j] == 2 or mt[i][j] == 6 or mt[i][j] == 5) : if (s2(i + 1, j)): push(i + 1, j, c + 1) if (mt[i][j] == 1 or mt[i][j] == 3 or mt[i][j] == 7 or mt[i][j] == 6) : if (s3(i, j - 1)): push(i, j - 1, c + 1) if (mt[i][j] == 1 or mt[i][j] == 2 or mt[i][j] == 4 or mt[i][j] == 7) : if (s4(i - 1, j)): push(i - 1, j, c + 1) if __name__=='__main__': # main function f = 0 r = 0 # matrix for i in range(row_size) : for j in range(col_size) : # visited matrix for BFS set to # unvisited for every cell vi[i][j] = 0 # depth set to max initial value depth[i][j] = Max if (mt[x][y] != 0): # condition for BFS bfs(x, y, 1) nc = 0 for i in range(row_size) : for j in range(col_size) : if (depth[i][j] <= l) : print("({}, {})".format(i,j),end='') nc+=1 print(" ",nc) |
(1, 0)(1, 1)(1, 2) 3
Complexity Analysis:
- Time Complexity: O(N * M) where N is the total number of rows and M is the total number of columns
- Auxiliary Space: O(N * M)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
