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.
<span”>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 columnsconsisting 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 01 12 21 32 43 54 65 56 47 38 29 110 011 112 213 314 413 512 611 710 8*********************….c………….**…-…………..**c……………..**………….-….**-.c……………**.-…………….**………..c……*********************safe=4infected=4Explanation: 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 01 12 23 34 45 56 47 38 29 310 49 58 67 76 85 74 63 52 41 30 2*********************………………**..c……………**….-………….**………-……..**………………**…….-……c…**………………*********************safe=2infected=3Explanation: 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++ program for the above approach // Funtion to print trajectory of the virus // and safe and infected citizens voidcoronaVirus(chararr[row][col]) // To store Inverted Array // Temporary array to store // To store number of infected citizens // To store total number of citizens (‘a’, ‘c’) for(inti = 0; i <= 8; i++) { for(intj = 0; j < 20; j++) { // Invert the array row wise inverted[i][j] = arr[8 – i][j]; // Count the number of citiens for(inti = 0; i <= 8; i++) { for(intj = 0; j < 20; j++) { // Count total number of citizens. || inverted[i][j] == ‘c’) { // Copy inverted array in temp temp[i][j] = inverted[i][j]; // To store number of times, // virus encountered a boundary // Variable for row-wise traversal // Variable for column-wise traversal // Variable to store direction // The virus starts from (0, 0) always // To break infinite looping // Finding trajectory and safe while(bound <= 1 && flag < 1000) { cout << i << ” “<< j << endl; // Virus has striked the boundary twice. if(inverted[j][i] == ‘*’&& bound == 1) { // Virus striked the corners, end loop if(inverted[j][i] == ‘*’) { if(i == 0 && j == 8 || i == 20 && j == 8 // First time for the virus if(inverted[j][i] == ‘*’&& bound == 0) { // Increment bound variable if(i == 0 && j != 8 && j != 0) { // Turns 90 degree clockwise // Else turns 90 degree anticlockwise // Strikes the right wall elseif(i == 20 && j != 0 && j != 8) { // Turns 90 degree anticlockwise // Else turns 90 degree clockwise // Strikes the upper wall elseif(j == 8 && i != 0 && i != 20) { // Turns 90 degree anticlockwise // Else turns 90 degree clockwise // Strikes the lower wall elseif(j == 0 && i != 0 && i != 20) { // Turns 90 degree clockwise // Else turns 90 degree anticlockwise // Make ‘c’ visited by replacing it by’-‘ if(inverted[j][i] == ‘c’) { // Turns all directions 90 // Increment count of infected citizens // Make ‘a’ visited by replacing it by’-‘ if(inverted[j][i] == ‘a’) { // Turns all directions by 90 degree // Increment the counter diagonally // in the given direction. if(inverted[j][i] == ‘.’) { // Print the mirror of the array // i.e. last row must be printed first. for(inti = 0; i <= 8; i++) { for(intj = 0; j < 20; j++) { // Print safe and infected citizens cout << “safe=”<< (total – count) << endl; cout << “infected=”<< (count) << endl; = { { ‘*’, ‘*’, ‘*’, ‘*’, ‘*’, ‘*’, ‘*’, ‘*’, ‘*’, ‘*’, ‘*’, ‘*’, ‘*’, ‘*’, ‘*’, ‘*’, ‘*’, ‘*’, ‘*’, ‘*’}, { ‘*’, ‘.’, ‘.’, ‘.’, ‘.’, ‘.’, ‘.’, ‘.’, ‘.’, ‘.’, ‘.’, ‘.’, ‘.’, ‘.’, ‘.’, ‘.’, ‘.’, ‘.’, ‘.’, ‘*’}, { ‘*’, ‘.’, ‘.’, ‘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
Time Complexity: O(R*C) where R is the number of rows and C is the number of columnsAuxiliary Space: O(R*C)
Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer Complete Interview Preparation Course.
In case you wish to attend live classes with experts, please refer DSA Live Classes for Working Professionals and Competitive Programming Live for Students.read more
