Given a grid of dimension, 2 rows * N columns and array Q[][2] of dimension M, the duty for this downside is to verify traversal from (1, 1) to (2, N) is feasible or not within the given grid for every question given X and Y, block cell (X, Y) whether it is open or open cell (X, Y) whether it is blocked. Initially, all cells are open for traversal.
Notice: Open cells enable traversal by means of that cell and blocked cell doesn’t enable traversal by means of that cell.
Examples:
Enter: N = 5, Q[][2] = {{2, 3}, {1, 4}, {2, 4}, {2, 3}, {1, 4}}
Output: Sure
No
No
No
Sure
Rationalization: Initially all cells are open for traversal
- question 1 : (2, 3) was open for traversal and now after performing first question it’s blocked. Traversal from (1, 1) to (2, N) remains to be potential.
- question 2 : (1, 4) was open for traversal and now after performing second question it’s blocked. Traversal from (1, 1) to (2, N) is just not potential.
- question 3 : (2, 4) was open for traversal and now after performing third question it’s blocked. Traversal from (1, 1) to (2, N) is just not potential.
- question 4 : (2, 3) was blocked for traversal and now after performing fourth question it’s open. Traversal from (1, 1) to (2, N) is just not potential.
- question 5 : (1, 4) was blocked for traversal and now after performing fifth question it’s open. Traversal from (1, 1) to (2, N) is feasible.
Enter: int N = 2, Q[][2] = {{2, 1}, {1, 2}, {1, 2}, {1, 2}};
Output: Sure
No
Sure
No
Naive strategy: The essential technique to resolve the issue is as follows:
The essential technique to resolve this downside is to replace grid for every question and with DFS (Depth First Search) verify if traversal from (1, 1) to (2, N) is feasible or not for every question.
Time Complexity: O(N * Q)
Auxiliary House: O(N)
Environment friendly Method: The above strategy may be optimized primarily based on the next thought:
- Grasping algorithms can be utilized to unravel this downside.
- Rely of Blocks may be tracked and if blocks are zero then reply will likely be “Sure” else “No”.
Comply with the steps under to unravel the issue:
- second array grid[2][N] is created initially with all values zero.
- variable CNT is created for monitoring the variety of blocks initially with a worth of zero.
- Iterating for every M question and for every question updating grid[2][N].
- if CNT is zero then print “Sure” or else “No” for every question.
Beneath is the implementation of the above strategy:
C++
// C++ code to implement the strategy
#embrace <bits/stdc++.h>
utilizing namespace std;
// Perform to verify if path from (1, 1)
// to (2, N) exist or not for every
// question
void countWays(int N, int Q[][2], int M)
{
// Simulating grid
vector<vector<int> > grid(2, vector<int>(N, 0));
// Counter that signifies variety of
// blockades
int cnt = 0;
// Iterating for all queries
for (int i = 0; i < M; i++) {
// X and Y for present question
int X = Q[i][0] - 1, Y = Q[i][1] - 1;
// If the present grid location
// is blocked
if (grid[X][Y]) {
// Open the present
// grid location
grid[X][Y] = 0;
// Just one blockade
if (Y == 0) {
// Eradicating single blokade
cnt = cnt - grid[X - 1][Y + 1];
}
// Just one blokade
else if (Y == N - 1) {
// Eradicating single blokade
cnt = cnt - grid[X + 1][Y - 1];
}
// Three blokades
else {
// Eradicating three blokades
cnt = cnt - grid[X ^ 1][Y - 1];
cnt = cnt - grid[X ^ 1][Y];
cnt = cnt - grid[X ^ 1][Y + 1];
}
}
// If the present grid location
// is open
else {
// Shut the present
// grid location
grid[X][Y] = 1;
// Just one blockade
if (Y == 0) {
// Eradicating single blokade
cnt = cnt + grid[X - 1][Y + 1];
}
// Just one blokade
else if (Y == N - 1) {
// Eradicating single blokade
cnt = cnt + grid[X + 1][Y - 1];
}
// Three blokades
else {
// Eradicating three blokades
cnt = cnt + grid[X ^ 1][Y - 1];
cnt = cnt + grid[X ^ 1][Y];
cnt = cnt + grid[X ^ 1][Y + 1];
}
}
// If there aren't any blokade
// print sure
if (cnt == 0)
cout << "Sure" << endl;
// If there are blokade
// print no
else
cout << "No" << endl;
}
}
// Driver Code
int most important()
{
// Enter 1
int N = 5, Q[][2] = {
{ 2, 3 }, { 1, 4 }, { 2, 4 }, { 2, 3 }, { 1, 4 }
};
int M = 5;
// Perform Name
countWays(N, Q, M);
cout << endl;
// Enter 2
int N1 = 2,
Q1[][2]
= { { 2, 1 }, { 1, 2 }, { 1, 2 }, { 1, 2 } };
int M1 = 4;
// Perform Name
countWays(N1, Q1, M1);
return 0;
}
Sure No No No Sure Sure No Sure No
Time Complexity: O(N + Q)
Auxiliary House: O(N)
Associated Articles:
