Problem Description:
A city is represented as a two-dimensional rectangular matrix. The outer wall of the given matrix denotes the boundaries of the city. Citizens are dispersed in the city at different locations. They are either depicted by {a, c}. Coronavirus has already infected the city.
The Coronavirus enters the city from coordinate (0, 0) and traverses along a diagonal path until it encounters a human. If it encounters a human, designated as a, its trajectory rotates anti-clockwise (right to left) by 90 degrees. Similarly, if it encounters a human, designated as c, its trajectory rotates clockwise (left to right) by 90 degrees. After infecting the person, the virus continues to move along its diagonal path.
During its traversal, if it hits the boundary of the city for the first time, it rotates 90 degrees to reenter the city. However, if it hits any of the boundary walls, the second time, the virus gets destroyed.
You have to calculate the trajectory taken by the virus, print the city map where infected citizens can be found and finally report the number of safe and infected citizens.
Input:
An input matrix of 9 rows and 20 columns consisting of characters “*”, “a”, “c” and “.” where
- “*” denotes an element on the boundaries of the city
- “a” denotes citizen after encountering whom the virus trajectory changes by 90 degrees (anti-clockwise direction)
- “c” denotes citizen after encountering whom the virus trajectory changes by 90 degrees (clockwise direction)
- “.” (dot) denotes an empty location within the city
Output:
A random number of lines each denoting the coordinates of the trajectory of the virus.
From the next line an output matrix of 9 rows and 20 columns consisting of characters “*”, “a”, “c”, “.” and “-” where
- “*” denotes an element on the boundaries of the city
- “a” denotes citizen after encountering whom the virus trajectory changes by 90 degrees (anti-clockwise direction)
- “c” denotes citizen after encountering whom the virus trajectory changes by 90 degrees (clockwise direction)
- “.” (dot) denotes an empty location within the city
- “-“ denotes the location of the infected citizen
And the next two lines print the number of safe and infected citizens in the city.
Constraints:
- 0 <= x <= 20
- 0 <= y <= 8
- The virus cannot hit the three corners (20, 8) (20, 0) (0, 8)
Examples:
Input:
********************
*….c………….*
*…c…………..*
*c……………..*
*………….a….*
*c.c……………*
*.a…………….*
*………..c……*
********************
Output:
0 0
1 1
2 2
1 3
2 4
3 5
4 6
5 5
6 4
7 3
8 2
9 1
10 0
11 1
12 2
13 3
14 4
13 5
12 6
11 7
10 8
********************
*….c………….*
*…-…………..*
*c……………..*
*………….-….*
*-.c……………*
*.-…………….*
*………..c……*
********************
safe=4
infected=4
Explanation: The virus trajectory starts from (0, 0) and crosses (1, 1) (2, 2). At (2, 2) we have a citizen of type a causing the virus trajectory to be rotated by 90 degrees anti-clockwise. It moves until the next citizen in its path is encountered at (1, 3) of type c causing the virus trajectory to be rotated by 90 degree clockwise. It continues on its path till it reaches the next human in its path at (4, 6) of type c Virus trajectory is again rotated by 90 degrees clockwise until it hits the boundary at (10, 0). Since this is the first time that the virus hits the boundary, it rotates by 90 degrees anticlockwise to reenter the city. The trajectory then continues towards (11, 1) (12, 2) (13, 3) and finally a citizen at (14, 4) of type a rotating the trajectory to 90 degree anticlockwise. From there it continues its trajectory and hits the boundary at (10, 8).
Since this is the second time the virus hits the boundary, the virus is destroyed.
So, along its trajectory starting from (0, 0) it has infected 4 citizens at location (2, 2) (1, 3) (4, 6) (14, 4). The other 4 citizens who did not come in the virus trajectory are deemed to be safe.Input:
********************
*………………*
*..c……………*
*….c………….*
*………a……..*
*………………*
*…….a……c…*
*………………*
********************
Output:
0 0
1 1
2 2
3 3
4 4
5 5
6 4
7 3
8 2
9 3
10 4
9 5
8 6
7 7
6 8
5 7
4 6
3 5
2 4
1 3
0 2
********************
*………………*
*..c……………*
*….-………….*
*………-……..*
*………………*
*…….-……c…*
*………………*
********************
safe=2
infected=3
Explanation: The virus trajectory starts from (0, 0) and crosses (1, 1) (2, 2) (5, 5). At (5, 5) we have a citizen of type c causing the virus trajectory to be rotated by 90 degrees clockwise. It moves until the next citizen in its path is encountered at (8, 2) of type a causing the virus trajectory to be rotated by 90 degree anti-clockwise. It continues on its path till it reaches the next human in its path at (10, 4) of type a Virus trajectory is again rotated by 90 degrees clockwise until it hits the boundary at (6, 8). Since this is the first time that the virus hits the boundary, it rotates by 90 degrees anticlockwise to reenter the city. The trajectory then continues towards (9, 5) (8, 6) (7, 7) (6, 8) and renters the city by rotating the trajectory by 90 degrees anti-clockwise to follow the trajectory (5, 7) (4, 6) (3, 5) (2, 4) (1, 3) (0, 2).
At (0, 2) it again hits the boundary and since this is the second time the virus hits the boundary, the virus is destroyed. So along its trajectory starting from (0, 0) it has infected 3 citizens at location (5, 5) (10, 4) (8, 2). The other 2 citizens who did not come in the virus trajectory are deemed to be safe.
Approach: The idea to solve this problem is to first invert the graph represented by the input and traverse the graph according to the given conditions. Follow the below steps to solve the problem:
- First, invert the input array in an inverted array. So the last row becomes the first and the second last the second and so on. This is done to view the graph in a two-dimension coordinate system with positive x and y.
- Traverse the graph and keep the track of the number of times the virus has hit the boundary in a variable named bound and run a while loop until the value of this variable is less than or equal to 1.
- Initialize a variable, direct, to hold the direction of motion as:
- If direct is 1, the direction is north-east.
- If direct is 2, the direction is north-west.
- If direct is 3, the direction is south-east.
- If direct is 4, the direction is south-west.
- The virus will have 4 directions of motion. The virus will start from the vertex (0, 0) with the direction of motion as 1(moving towards the north-east). The direction of the variable is changed when it encounters a wall.
- Also, when ‘a’ is encountered, change the value of direct to the resulting anti-clockwise direction and when ‘c’ is encountered, change the value of direct to 90 degrees clockwise from the current direction.
- For the ‘.’ (dot) character in the matrix, keep incrementing or decrementing the current position variables by 1 to move diagonally in the direct variable’s depicted direction.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; #define row 9 #define col 20 // Function to print trajectory of the virus // and safe and infected citizens void coronaVirus( char arr[row][col]) { // To store Inverted Array char inverted[9][20]; // Temporary array to store // original array char temp[9][20]; // To store number of infected citizens int count = 0; // To store total number of citizens ('a', 'c') int total = 0; // To invert the array for ( int i = 0; i <= 8; i++) { for ( int j = 0; j < 20; j++) { // Invert the array row wise inverted[i][j] = arr[8 - i][j]; } } // Count the number of citizens for ( int i = 0; i <= 8; i++) { for ( int j = 0; j < 20; j++) { // Count total number of citizens. if (inverted[i][j] == 'a' || inverted[i][j] == 'c' ) { total++; } // Copy inverted array in temp temp[i][j] = inverted[i][j]; } } // To store number of times, // virus encountered a boundary int bound = 0; // Variable for row-wise traversal int i = 1; // Variable for column-wise traversal int j = 1; // Variable to store direction int direct = 1; // The virus starts from (0, 0) always cout << "0 0" << endl; // To break infinite looping int flag = 0; // Finding trajectory and safe // and infected citizens while (bound <= 1 && flag < 1000) { flag++; cout << i << " " << j << endl; // Virus has striked the boundary twice. // Therefore, end loop if (inverted[j][i] == '*' && bound == 1) { break ; } // Virus striked the corners, end loop if (inverted[j][i] == '*' ) { if (i == 0 && j == 8 || i == 20 && j == 8 || i == 20 && j == 0) { break ; } } // First time for the virus // to hit the boundary if (inverted[j][i] == '*' && bound == 0) { // Increment bound variable bound++; // Strikes the left wall if (i == 0 && j != 8 && j != 0) { // Turns 90 degree clockwise if (direct == 2) { direct = 1; i++; j++; } // Else turns 90 degree anticlockwise else if (direct == 4) { direct = 3; j--; i++; } } // Strikes the right wall else if (i == 20 && j != 0 && j != 8) { // Turns 90 degree anticlockwise if (direct == 1) { direct = 2; i--; j++; } // Else turns 90 degree clockwise else if (direct == 3) { direct = 4; i--; j--; } } // Strikes the upper wall else if (j == 8 && i != 0 && i != 20) { // Turns 90 degree anticlockwise if (direct == 2) { direct = 4; i--; j--; } // Else turns 90 degree clockwise else if (direct == 1) { direct = 3; j--; i++; } } // Strikes the lower wall else if (j == 0 && i != 0 && i != 20) { // Turns 90 degree clockwise if (direct == 4) { direct = 2; i--; j++; } // Else turns 90 degree anticlockwise else if (direct == 3) { direct = 1; i++; j++; } } continue ; } // Make 'c' visited by replacing it by'-' if (inverted[j][i] == 'c' ) { temp[j][i] = '-' ; // Turns all directions 90 // degree clockwise if (direct == 1) { direct = 3; j--; i++; } else if (direct == 2) { direct = 1; i++; j++; } else if (direct == 3) { direct = 4; i--; j--; } else if (direct == 4) { direct = 2; i--; j++; } // Increment count of infected citizens count++; continue ; } // Make 'a' visited by replacing it by'-' if (inverted[j][i] == 'a' ) { temp[j][i] = '-' ; // Turns all directions by 90 degree // anticlockwise if (direct == 1) { direct = 2; i--; j++; } else if (direct == 2) { direct = 4; i--; j--; } else if (direct == 3) { direct = 1; i++; j++; } else if (direct == 4) { direct = 3; j--; i++; } // Increment count of // infected citizens count++; continue ; } // Increment the counter diagonally // in the given direction. if (inverted[j][i] == '.' ) { if (direct == 1) { i++; j++; } else if (direct == 2) { i--; j++; } else if (direct == 3) { j--; i++; } else if (direct == 4) { i--; j--; } continue ; } } // Print the mirror of the array // i.e. last row must be printed first. for ( int i = 0; i <= 8; i++) { for ( int j = 0; j < 20; j++) { cout << temp[8 - i][j]; } cout << endl; } // Print safe and infected citizens cout << "safe=" << (total - count) << endl; cout << "infected=" << (count) << endl; } // Driver Code int main() { // Given 2D array char arr[row][col] = { { '*' , '*' , '*' , '*' , '*' , '*' , '*' , '*' , '*' , '*' , '*' , '*' , '*' , '*' , '*' , '*' , '*' , '*' , '*' , '*' }, { '*' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '*' }, { '*' , '.' , '.' , 'c' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '*' }, { '*' , '.' , '.' , '.' , '.' , 'c' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '*' }, { '*' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , 'a' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '*' }, { '*' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '*' }, { '*' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , 'a' , '.' , '.' , '.' , '.' , '.' , '.' , 'c' , '.' , '.' , '.' , '*' }, { '*' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '.' , '*' }, { '*' , '*' , '*' , '*' , '*' , '*' , '*' , '*' , '*' , '*' , '*' , '*' , '*' , '*' , '*' , '*' , '*' , '*' , '*' , '*' } }; // Function Call coronaVirus(arr); return 0; } |
0 0 1 1 2 2 3 3 4 4 5 5 6 4 7 3 8 2 9 3 10 4 9 5 8 6 7 7 6 8 5 7 4 6 3 5 2 4 1 3 0 2 ******************** *..................* *..c...............* *....-.............* *.........-........* *..................* *.......-......c...* *..................* ******************** safe=2 infected=3
Time Complexity: O(R*C) where R is the number of rows and C is the number of columns
Auxiliary Space: O(R*C)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!