Corona Virus | TCS Codevita 2020
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++ 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;
}
import java.util.Arrays;
public class Main {
// Constants for the size of the grid
private static final int ROW = 9;
private static final int COL = 20;
// Function to print trajectory of the virus and safe and infected citizens
public static void coronaVirus(char[][] arr) {
// To store Inverted Array
char[][] inverted = new char[ROW][COL];
// Temporary array to store original array
char[][] temp = new char[ROW][COL];
// 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 < ROW; i++) {
for (int j = 0; j < COL; j++) {
// Invert the array row wise
inverted[i][j] = arr[ROW - 1 - i][j];
}
}
// Count the number of citizens
for (int i = 0; i < ROW; i++) {
for (int j = 0; j < COL; 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
System.out.println("0 0");
// To break infinite looping
int flag = 0;
// Finding trajectory and safe and infected citizens
while (bound <= 1 && flag < 1000) {
flag++;
System.out.println(i + " " + j);
// 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 == ROW - 1 || i == COL - 1 && j == ROW - 1 || i == COL - 1 && 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 != ROW - 1 && 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 == COL - 1 && j != 0 && j != ROW - 1) {
// 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 == ROW - 1 && i != 0 && i != COL - 1) {
// 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 != COL - 1) {
// 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 k = 0; k < ROW; k++) {
for (int l = 0; l < COL; l++) {
System.out.print(temp[ROW - 1 - k][l]);
}
System.out.println();
}
// Print safe and infected citizens
System.out.println("safe=" + (total - count));
System.out.println("infected=" + count);
}
// Driver Code
public static void main(String[] args) {
// Given 2D array
char[][] arr = {
{ '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' },
{ '*', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '*' },
{ '*', '.', '.', 'c', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '*' },
{ '*', '.', '.', '.', '.', 'c', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '*' },
{ '*', '.', '.', '.', '.', '.', '.', '.', '.', '.', 'a', '.', '.', '.', '.', '.', '.', '.', '.', '*' },
{ '*', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '*' },
{ '*', '.', '.', '.', '.', '.', '.', '.', 'a', '.', '.', '.', '.', '.', '.', 'c', '.', '.', '.', '*' },
{ '*', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '*' },
{ '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*' }
};
// Function Call
coronaVirus(arr);
}
}
def coronaVirus(arr):
# Constants for the size of the grid
ROW = 9
COL = 20
# To store Inverted Array
inverted = [[0 for _ in range(COL)] for _ in range(ROW)]
# Temporary array to store original array
temp = [[0 for _ in range(COL)] for _ in range(ROW)]
# To store number of infected citizens
count = 0
# To store total number of citizens ('a', 'c')
total = 0
# To invert the array
for i in range(ROW):
for j in range(COL):
# Invert the array row wise
inverted[i][j] = arr[ROW - 1 - i][j]
# Count the number of citizens
for i in range(ROW):
for j in range(COL):
# Count total number of citizens.
if inverted[i][j] == 'a' or inverted[i][j] == 'c':
total += 1
# Copy inverted array in temp
temp[i][j] = inverted[i][j]
# To store number of times, virus encountered a boundary
bound = 0
# Variable for row-wise traversal
i = 1
# Variable for column-wise traversal
j = 1
# Variable to store direction
direct = 1
# The virus starts from (0, 0) always
print("0 0")
# To break infinite looping
flag = 0
# Finding trajectory and safe and infected citizens
while bound <= 1 and flag < 1000:
flag += 1
print(i, j)
# Virus has striked the boundary twice. Therefore, end loop
if inverted[j][i] == '*' and bound == 1:
break
# Virus striked the corners, end loop
if inverted[j][i] == '*':
if (i == 0 and j == ROW - 1) or (i == COL - 1 and j == ROW - 1) or (i == COL - 1 and j == 0):
break
# First time for the virus to hit the boundary
if inverted[j][i] == '*' and bound == 0:
# Increment bound variable
bound += 1
# Strikes the left wall
if i == 0 and j != ROW - 1 and j != 0:
# Turns 90 degree clockwise
if direct == 2:
direct = 1
i += 1
j += 1
elif direct == 4:
direct = 3
j -= 1
i += 1
# Strikes the right wall
elif i == COL - 1 and j != 0 and j != ROW - 1:
# Turns 90 degree anticlockwise
if direct == 1:
direct = 2
i -= 1
j += 1
elif direct == 3:
direct = 4
i -= 1
j -= 1
# Strikes the upper wall
elif j == ROW - 1 and i != 0 and i != COL - 1:
# Turns 90 degree anticlockwise
if direct == 2:
direct = 4
i -= 1
j -= 1
elif direct == 1:
direct = 3
j -= 1
i += 1
# Strikes the lower wall
elif j == 0 and i != 0 and i != COL - 1:
# Turns 90 degree clockwise
if direct == 4:
direct = 2
i -= 1
j += 1
elif direct == 3:
direct = 1
i += 1
j += 1
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 -= 1
i += 1
elif direct == 2:
direct = 1
i += 1
j += 1
elif direct == 3:
direct = 4
i -= 1
j -= 1
elif direct == 4:
direct = 2
i -= 1
j += 1
# Increment count of infected citizens
count += 1
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 -= 1
j += 1
elif direct == 2:
direct = 4
i -= 1
j -= 1
elif direct == 3:
direct = 1
i += 1
j += 1
elif direct == 4:
direct = 3
j -= 1
i += 1
# Increment count of infected citizens
count += 1
continue
# Increment the counter diagonally in the given direction.
if inverted[j][i] == '.':
if direct == 1:
i += 1
j += 1
elif direct == 2:
i -= 1
j += 1
elif direct == 3:
j -= 1
i += 1
elif direct == 4:
i -= 1
j -= 1
continue
# Print the mirror of the array i.e. last row must be printed first.
for k in range(ROW):
row = ''
for l in range(COL):
row += temp[ROW - 1 - k][l]
print(row)
# Print safe and infected citizens
print("safe=" + str(total - count))
print("infected=" + str(count))
# Given 2D array
arr = [
['*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*'],
['*', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '*'],
['*', '.', '.', 'c', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '*'],
['*', '.', '.', '.', '.', 'c', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '*'],
['*', '.', '.', '.', '.', '.', '.', '.', '.', '.', 'a', '.', '.', '.', '.', '.', '.', '.', '.', '*'],
['*', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '*'],
['*', '.', '.', '.', '.', '.', '.', '.', 'a', '.', '.', '.', '.', '.', '.', 'c', '.', '.', '.', '*'],
['*', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '*'],
['*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*']
]
# Function Call
coronaVirus(arr)
// Function to print trajectory of the virus and safe and infected citizens
function coronaVirus(arr) {
// Constants for the size of the grid
const ROW = 9;
const COL = 20;
// To store Inverted Array
const inverted = [];
// Temporary array to store original array
const temp = [];
// To store number of infected citizens
let count = 0;
// To store total number of citizens ('a', 'c')
let total = 0;
// To invert the array
for (let i = 0; i < ROW; i++) {
inverted.push([]);
temp.push([]);
for (let j = 0; j < COL; j++) {
// Invert the array row wise
inverted[i][j] = arr[ROW - 1 - i][j];
}
}
// Count the number of citizens
for (let i = 0; i < ROW; i++) {
for (let j = 0; j < COL; 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
let bound = 0;
// Variable for row-wise traversal
let i = 1;
// Variable for column-wise traversal
let j = 1;
// Variable to store direction
let direct = 1;
// The virus starts from (0, 0) always
console.log("0 0");
// To break infinite looping
let flag = 0;
// Finding trajectory and safe and infected citizens
while (bound <= 1 && flag < 1000) {
flag++;
console.log(i + " " + j);
// 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 === ROW - 1) || (i === COL - 1 && j === ROW - 1) || (i === COL - 1 && 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 !== ROW - 1 && j !== 0) {
// Turns 90 degree clockwise
if (direct === 2) {
direct = 1;
i++;
j++;
} else if (direct === 4) {
direct = 3;
j--;
i++;
}
}
// Strikes the right wall
else if (i === COL - 1 && j !== 0 && j !== ROW - 1) {
// Turns 90 degree anticlockwise
if (direct === 1) {
direct = 2;
i--;
j++;
} else if (direct === 3) {
direct = 4;
i--;
j--;
}
}
// Strikes the upper wall
else if (j === ROW - 1 && i !== 0 && i !== COL - 1) {
// Turns 90 degree anticlockwise
if (direct === 2) {
direct = 4;
i--;
j--;
} else if (direct === 1) {
direct = 3;
j--;
i++;
}
}
// Strikes the lower wall
else if (j === 0 && i !== 0 && i !== COL - 1) {
// Turns 90 degree clockwise
if (direct === 4) {
direct = 2;
i--;
j++;
} 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 (let k = 0; k < ROW; k++) {
let row = "";
for (let l = 0; l < COL; l++) {
row += temp[ROW - 1 - k][l];
}
console.log(row);
}
// Print safe and infected citizens
console.log("safe=" + (total - count));
console.log("infected=" + count);
}
// Given 2D array
const arr = [
['*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*'],
['*', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '*'],
['*', '.', '.', 'c', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '*'],
['*', '.', '.', '.', '.', 'c', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '*'],
['*', '.', '.', '.', '.', '.', '.', '.', '.', '.', 'a', '.', '.', '.', '.', '.', '.', '.', '.', '*'],
['*', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '*'],
['*', '.', '.', '.', '.', '.', '.', '.', 'a', '.', '.', '.', '.', '.', '.', 'c', '.', '.', '.', '*'],
['*', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '.', '*'],
['*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*', '*']
];
// Function Call
coronaVirus(arr);
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 columns
Auxiliary Space: O(R*C)