Descripción del problema:
Una ciudad se representa como una array rectangular bidimensional. El muro exterior de la array dada denota los límites de la ciudad. Los ciudadanos están dispersos en la ciudad en diferentes lugares. Están representados por {a, c} . El coronavirus ya contagió a la ciudad.
El coronavirus ingresa a la ciudad desde la coordenada (0, 0) y atraviesa un camino diagonal hasta que se encuentra con un humano. Si se encuentra con un ser humano, designado como , su trayectoria gira en sentido contrario a las agujas del reloj (de derecha a izquierda) 90 grados . De manera similar, si se encuentra con un ser humano, designado como c , su trayectoria gira en el sentido de las agujas del reloj (de izquierda a derecha) 90 grados . Después de infectar a la persona, el virus continúa moviéndose a lo largo de su camino diagonal.
Durante su recorrido, si llega al límite de la ciudad por primera vez, gira 90 grados para volver a entrar en la ciudad. Sin embargo, si golpea cualquiera de los muros fronterizos, la segunda vez, el virus se destruye.
Tienes que calcular la trayectoria que ha tomado el virus, imprimir el mapa de la ciudad donde se encuentran los ciudadanos infectados y finalmente reportar el número de ciudadanos seguros e infectados.
Aporte:
Una array de entrada de 9 filas y 20 columnas que consta de los caracteres “ *” , “a” , “c” y “.” dónde
- “*” denota un elemento en los límites de la ciudad
- «a» denota ciudadano después de encontrar a quien la trayectoria del virus cambia en 90 grados (en sentido contrario a las agujas del reloj)
- «c» denota ciudadano después de encontrar a quien la trayectoria del virus cambia en 90 grados (sentido horario)
- “.” (punto) denota una ubicación vacía dentro de la ciudad
Producción:
Un número aleatorio de líneas, cada una de las cuales indica las coordenadas de la trayectoria del virus.
Desde la siguiente línea, una array de salida de 9 filas y 20 columnas que consta de los caracteres » *» , «a» , «c» , «.» y “-” donde
- “*” denota un elemento en los límites de la ciudad
- «a» denota ciudadano después de encontrar a quien la trayectoria del virus cambia en 90 grados (en sentido contrario a las agujas del reloj)
- «c» denota ciudadano después de encontrar a quien la trayectoria del virus cambia en 90 grados (sentido horario)
- “.” (punto) denota una ubicación vacía dentro de la ciudad
- «-« indica la ubicación del ciudadano infectado
Y las siguientes dos líneas imprimen el número de ciudadanos seguros e infectados en la ciudad.
Restricciones:
- 0 <= x <= 20
- 0 <= y <= 8
- El virus no puede golpear las tres esquinas (20, 8) (20, 0) (0, 8)
Ejemplos:
Entrada:
********************
*….c………….*
*…c…………..*
*c………………. .*
*………….a….*
*cc………………*
*.a……………….*
*…………..c……*
********** **********
Salida:
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……*
****** **************
seguro=4
infectado=4
Explicación:La trayectoria del virus comienza en (0, 0) y cruza (1, 1) (2, 2). En (2, 2) tenemos un ciudadano de tipo a que hace que la trayectoria del virus gire 90 grados en sentido contrario a las agujas del reloj. Se mueve hasta que el próximo ciudadano en su camino se encuentra en (1, 3) de tipo c, lo que hace que la trayectoria del virus gire 90 grados en el sentido de las agujas del reloj. Continúa en su camino hasta que alcanza al siguiente humano en su camino en (4, 6) de tipo c. La trayectoria del virus se gira nuevamente 90 grados en el sentido de las agujas del reloj hasta que llega al límite en (10, 0). Dado que esta es la primera vez que el virus toca el límite, gira 90 grados en el sentido contrario a las agujas del reloj para volver a entrar en la ciudad. La trayectoria luego continúa hacia (11, 1) (12, 2) (13, 3) y finalmente un ciudadano en (14, 4) de tipo a girando la trayectoria 90 grados en sentido antihorario. Desde allí continúa su trayectoria y llega al límite en (10,
Dado que esta es la segunda vez que el virus llega al límite, el virus se destruye.
Entonces, a lo largo de su trayectoria a partir de (0, 0) ha infectado a 4 ciudadanos en la ubicación (2, 2) (1, 3) (4, 6) (14, 4). Se considera que los otros 4 ciudadanos que no entraron en la trayectoria del virus están a salvo.Entrada:
*******************
*………………*
*..c………………*
*….c………….*
*………a……..*
*………………*
*…….a……c…*
*………………*
************** ******
Salida:
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…*
*………………*
**************** ****
seguro=2
infectado=3
Explicación:La trayectoria del virus comienza desde (0, 0) y cruza (1, 1) (2, 2) (5, 5). En (5, 5) tenemos un ciudadano de tipo c que hace que la trayectoria del virus gire 90 grados en el sentido de las agujas del reloj. Se mueve hasta que se encuentra con el próximo ciudadano en su camino en (8, 2) de tipo a, lo que hace que la trayectoria del virus gire 90 grados en sentido contrario a las agujas del reloj. Continúa en su camino hasta que alcanza al siguiente humano en su camino en (10, 4) de tipo a. La trayectoria del virus se gira nuevamente 90 grados en el sentido de las agujas del reloj hasta que llega al límite en (6, 8). Dado que esta es la primera vez que el virus toca el límite, gira 90 grados en el sentido contrario a las agujas del reloj para volver a entrar en la ciudad. Luego, la trayectoria continúa hacia (9, 5) (8, 6) (7, 7) (6, 8) y entra en la ciudad girando la trayectoria 90 grados en el sentido contrario a las agujas del reloj para seguir la trayectoria (5, 7) (4 , 6) (3, 5) (2, 4) (1, 3) (0, 2).
En (0, 2) vuelve a tocar el límite y, dado que es la segunda vez que el virus toca el límite, el virus se destruye. Entonces, a lo largo de su trayectoria a partir de (0, 0), ha infectado a 3 ciudadanos en la ubicación (5, 5) (10, 4) (8, 2). Se considera que los otros 2 ciudadanos que no entraron en la trayectoria del virus están a salvo.
Enfoque: La idea para resolver este problema es primero invertir el gráfico representado por la entrada y atravesar el gráfico de acuerdo con las condiciones dadas. Siga los pasos a continuación para resolver el problema:
- Primero, invierta la array de entrada en una array invertida. Entonces la última fila se convierte en la primera y la penúltima en la segunda y así sucesivamente. Esto se hace para ver el gráfico en un sistema de coordenadas de dos dimensiones con x e y positivas .
- Recorra el gráfico y lleve la cuenta de la cantidad de veces que el virus ha tocado el límite en una variable denominada límite y ejecute un ciclo while hasta que el valor de esta variable sea menor o igual a 1 .
- Inicialice una variable, direct , para mantener la dirección del movimiento como:
- Si directo es 1, la dirección es noreste.
- Si directo es 2, la dirección es noroeste.
- Si directo es 3, la dirección es sureste.
- Si directo es 4, la dirección es suroeste.
- El virus tendrá 4 direcciones de movimiento. El virus comenzará desde el vértice (0, 0) con la dirección de movimiento 1 (moviéndose hacia el noreste). La dirección de la variable cambia cuando se encuentra con una pared.
- Además, cuando se encuentre ‘a’ , cambie el valor de direct a la dirección antihoraria resultante y cuando se encuentre ‘c’ , cambie el valor de direct a 90 grados en el sentido de las agujas del reloj desde la dirección actual.
- Para el ‘.’ (punto) en la array, siga aumentando o disminuyendo las variables de posición actual en 1 para moverse en diagonal en la dirección representada de la variable directa .
A continuación se muestra la implementación del enfoque anterior:
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
Complejidad de tiempo: O(R*C) donde R es el número de filas y C es el número de columnas
Espacio auxiliar: O(R*C)