Nos dan una array m*n que puede tener un número entre 0 y 7. Cada número representa una tubería con la siguiente forma:
Dos tuberías se consideran conectadas si sus extremos se conectan.
Ejemplo:
Si la array es la siguiente:
0040
1360
5000
Tubería 1 y 3{1 abre a la derecha. 3 abre a la izquierda} están conectados. Otros tubos conectados son 3 y 6 (3 se abre a la derecha. 6 se abre a la izquierda).
4 y 6 no están conectados ya que 6 no se abre hacia arriba y 4 no se abre hacia abajo.
1 y 5 tampoco están conectados, ya que aunque 1 se abre hacia abajo, 5 no está abierto hacia arriba.
Dada esta array, el punto de inicio (X, Y) y la longitud de la herramienta de sonda «L», averigüe cuántas tuberías {elementos de la array} se pueden alcanzar.
Nota: Herramienta de sonda: es una herramienta de medición, si se pueden alcanzar 6 tuberías pero la longitud de la herramienta de sonda es 4. La respuesta será 4 si se pueden alcanzar 3 tuberías pero la longitud de la herramienta de sonda es 4. La respuesta será 3.
Ejemplo:
Índice inicial: (1, 0)
Longitud de la sonda: 4
Array:
0040
1360
5000
tuberías conectadas a través de la sonda- (1, 0)->(1, 1)->(1, 2)
Respuesta- 3
Índice inicial: (0, 0)
Longitud de sonda: 4
Array:
0040
1360
5000
tuberías conectadas mediante sonda- 0
Respuesta- 0
Índice inicial: (1, 0)
Longitud de sonda: 2
Array:
0040
1360
5000
tuberías conectadas mediante sonda- (1, 0 ) 0)->(1, 1)
Respuesta- 2
Pasos clave para resolver:
encontrar a cuál de los elementos de tubería vecinos se puede acceder desde un punto de partida {Mantener una lista exhaustiva de controles para determinar los criterios vecinos como se definió anteriormente}.
Encuentre un método para procesar a través de los elementos para encontrar el siguiente conjunto de elementos a los que se puede acceder. {Recorriendo el gráfico}. Cabe señalar que deseamos llegar a todos los Nodes a los que se puede acceder desde el Node de inicio con una distancia inferior a «L». El enfoque no está en llegar a muchos Nodes, sino en llegar a ellos con menos movimientos desde el punto de inicio (X, Y).
Recursividad:
marcamos todos los Nodes como no visitados y el número de Nodes visitados es 0. Si un Node marcado como no visitado se procesa durante la recursividad, incremente el número de Nodes visitados en 1 y márquelo como visitado.
Comenzamos visitando el Node de inicio (X, Y) y luego visitando recursivamente todos sus vecinos conectados (según las comprobaciones de los criterios conectados como se definió anteriormente) hasta la profundidad de recurrencia de «L».
Inconveniente:
en el caso de una array altamente conectada (casi todas las tuberías están conectadas entre sí y existen múltiples formas de llegar a una tubería), llegamos a un Node varias veces y lo procesamos varias veces, lo que puede conducir a un tiempo de ejecución elevado. Podemos optimizarlo comprobando que volvemos a procesar un Node solo si lo hemos alcanzado con un nivel de recursión más bajo.
Esta no es una solución DFS porque reprocesamos un Node, incluso si ya se ha visitado, ya que es posible que la nueva visita actualice la profundidad de visita del Node a un nivel más bajo y se alcance una mayor profundidad después de este Node.
Búsqueda en amplitud:
marcamos todos los Nodes como no visitados y el número de Nodes visitados es 0. Si un Node marcado como no visitado se procesa durante el procesamiento, incrementamos el número de Nodes visitados en 1.
Comenzamos empujando el Node de inicio (X, Y) a una cola con profundidad 1 y luego comience a procesar la cola hasta que esté vacía.
En cada iteración se saca un miembro de la cola y se analizan sus vecinos conectados. Si los vecinos no están visitados y la profundidad del elemento actual no es mayor que L, los elementos conectados se ponen en cola, se marcan como visitados y el recuento de Nodes visitados aumenta en 1.
Como BFS realiza el recorrido de los Nodes por orden de nivel, no es posible que un Node visitado sea alcanzado en una distancia menor. Por lo tanto, el inconveniente del método anterior no puede existir. Esta es la solución óptima para este problema.
Simplificación posible en las soluciones para una codificación fácil:
dado que hay 7 tipos de tuberías, tendremos que poner múltiples condiciones if que conduzcan a declaraciones if anidadas que son difíciles de depurar. Se puede simplificar convirtiendo los 7 valores en datos basados en la dirección. Por ejemplo, cada valor se puede transformar en una estructura con 4 variables booleanas, una para cada dirección. Alternativamente, cada número se puede asignar a un número de 4 bits donde cada bit representa una dirección. Después de esta reducción de insumos, los controles serán más simples y menos complejos.
C++
#include <bits/stdc++.h>
using namespace std;
#define Max 1000
#define row_size 3
#define col_size 4
int x = 1, y = 0; // starting index(x, y),
int l = 4; // length of probe tool
// input matrix containing the pipes
int mt[row_size][col_size] = { { 0, 0, 4, 0 },
{ 1, 3, 6, 0 },
{ 5, 0, 0, 0 } };
// visited matrix checks for cells already visited
int vi[row_size][col_size];
// calculates the depth of connection for each cell
int depth[row_size][col_size];
int f = 0;
int r = 0;
// queue for BFS
struct node {
int x;
int y;
int d;
};
node q[Max];
void push(int a, int b, int d) // push function
{
node temp;
temp.x = a;
temp.y = b;
temp.d = d;
q[r++] = temp;
vi[a][b] = 1;
}
node pop() // pop function
{
node temp;
temp.x = q[f].x;
temp.y = q[f].y;
temp.d = q[f].d;
f++;
return temp;
}
// It can be simplified by converting the 7
// values into direction based data. For e.g.
// each value can be transformed into a structure
// with 4 Boolean variables, one for each direction.
// Alternatively, each number can be mapped to a 4
// bit number where each bit represents a direction.
bool s1(int i, int j) // conversion to final direction
{
if (i >= 0 && i < row_size && j >= 0 &&
j < col_size && vi[i][j] == 0 && (mt[i][j] == 1 ||
mt[i][j] == 3 || mt[i][j] == 6 || mt[i][j] == 7))
return true;
else
return false;
}
bool s2(int i, int j) // conversion to final direction
{
if (i >= 0 && i < row_size && j >= 0 && j < col_size &&
vi[i][j] == 0 && (mt[i][j] == 1 || mt[i][j] == 2 ||
mt[i][j] == 4 || mt[i][j] == 7))
return true;
else
return false;
}
bool s3(int i, int j) // conversion to final direction
{
if (i >= 0 && i < row_size && j >= 0 && j < col_size &&
vi[i][j] == 0 && (mt[i][j] == 1 || mt[i][j] == 3 ||
mt[i][j] == 4 || mt[i][j] == 5))
return true;
else
return false;
}
bool s4(int i, int j) // conversion to final direction
{
if (i >= 0 && i < row_size && j >= 0 && j < col_size &&
vi[i][j] == 0 && (mt[i][j] == 1 || mt[i][j] == 2 ||
mt[i][j] == 6 || mt[i][j] == 5))
return true;
else
return false;
}
// search for connection
// We start by pushing the start node (X, Y) into a queue
// with depth 1 and then start processing the queue till
// it is empty.
void bfs(int x, int y, int d)
{
push(x, y, d);
while (r > f) {
node temp = pop();
int i = temp.x;
int j = temp.y;
int c = temp.d;
depth[i][j] = c;
if (mt[i][j] == 1 || mt[i][j] == 3 ||
mt[i][j] == 4 || mt[i][j] == 5) {
if (s1(i, j + 1))
push(i, j + 1, c + 1);
}
if (mt[i][j] == 1 || mt[i][j] == 2 ||
mt[i][j] == 6 || mt[i][j] == 5) {
if (s2(i + 1, j))
push(i + 1, j, c + 1);
}
if (mt[i][j] == 1 || mt[i][j] == 3 ||
mt[i][j] == 7 || mt[i][j] == 6) {
if (s3(i, j - 1))
push(i, j - 1, c + 1);
}
if (mt[i][j] == 1 || mt[i][j] == 2 ||
mt[i][j] == 4 || mt[i][j] == 7) {
if (s4(i - 1, j))
push(i - 1, j, c + 1);
}
}
}
int main() // main function
{
f = 0;
r = 0;
// matrix
for (int i = 0; i < row_size; i++) {
for (int j = 0; j < col_size; j++) {
// visited matrix for BFS set to
// unvisited for every cell
vi[i][j] = 0;
// depth set to max initial value
depth[i][j] = Max;
}
}
if (mt[x][y] != 0) // condition for BFS
bfs(x, y, 1);
int nc = 0;
for (int i = 0; i < row_size; i++) {
for (int j = 0; j < col_size; j++) {
if (depth[i][j] <= l) {
cout << "(" << i << ", " << j << ")";
nc++;
}
}
}
cout << " " << nc << "\n";
}
Python3
Max=1000
row_size=3
col_size=4
x = 1; y = 0 # starting index(x, y),
l = 4 # length of probe tool
# input matrix containing the pipes
mt = [[ 0, 0, 4, 0 ,],
[ 1, 3, 6, 0],
[ 5, 0, 0, 0],]
# visited matrix checks for cells already visited
vi=[[False for _ in range(col_size)]for _ in range(row_size)]
# calculates the depth of connection for each cell
depth=[[0 for _ in range(col_size)] for _ in range(row_size)]
f = 0
r = 0
# queue for BFS
class node:
def __init__(self,x,y,d):
self.x=x
self.y=y
self.d=d
q=[None for _ in range(Max)]
def push(a, b, d): # push function
global r
temp=node(a,b,d)
q[r] = temp
r+=1
vi[a][b] = 1
def pop(): # pop function
global f
temp=node(q[f].x,q[f].y,q[f].d)
f+=1
return temp
# It can be simplified by converting the 7
# values into direction based data. For e.g.
# each value can be transformed into a structure
# with 4 Boolean variables, one for each direction.
# Alternatively, each number can be mapped to a 4
# bit number where each bit represents a direction.
def s1(i, j): # conversion to final direction
if (i >= 0 and i < row_size and j >= 0 and
j < col_size and vi[i][j] == 0 and (mt[i][j] == 1 or
mt[i][j] == 3 or mt[i][j] == 6 or mt[i][j] == 7)):
return True
else:
return False
def s2(i, j): # conversion to final direction
if (i >= 0 and i < row_size and j >= 0 and j < col_size and
vi[i][j] == 0 and (mt[i][j] == 1 or mt[i][j] == 2 or
mt[i][j] == 4 or mt[i][j] == 7)):
return True
else:
return False
def s3(i, j): # conversion to final direction
if (i >= 0 and i < row_size and j >= 0 and j < col_size and
vi[i][j] == 0 and (mt[i][j] == 1 or mt[i][j] == 3 or
mt[i][j] == 4 or mt[i][j] == 5)):
return True
else:
return False
def s4(i, j): # conversion to final direction
if (i >= 0 and i < row_size and j >= 0 and j < col_size and
vi[i][j] == 0 and (mt[i][j] == 1 or mt[i][j] == 2 or
mt[i][j] == 6 or mt[i][j] == 5)):
return True
else:
return False
# search for connection
# We start by pushing the start node (X, Y) into a queue
# with depth 1 and then start processing the queue till
# it is empty.
def bfs(x, y, d):
push(x, y, d)
while (r > f) :
temp = pop()
i = temp.x
j = temp.y
c = temp.d
depth[i][j] = c
if (mt[i][j] == 1 or mt[i][j] == 3 or
mt[i][j] == 4 or mt[i][j] == 5) :
if (s1(i, j + 1)):
push(i, j + 1, c + 1)
if (mt[i][j] == 1 or mt[i][j] == 2 or
mt[i][j] == 6 or mt[i][j] == 5) :
if (s2(i + 1, j)):
push(i + 1, j, c + 1)
if (mt[i][j] == 1 or mt[i][j] == 3 or
mt[i][j] == 7 or mt[i][j] == 6) :
if (s3(i, j - 1)):
push(i, j - 1, c + 1)
if (mt[i][j] == 1 or mt[i][j] == 2 or
mt[i][j] == 4 or mt[i][j] == 7) :
if (s4(i - 1, j)):
push(i - 1, j, c + 1)
if __name__=='__main__': # main function
f = 0
r = 0
# matrix
for i in range(row_size) :
for j in range(col_size) :
# visited matrix for BFS set to
# unvisited for every cell
vi[i][j] = 0
# depth set to max initial value
depth[i][j] = Max
if (mt[x][y] != 0): # condition for BFS
bfs(x, y, 1)
nc = 0
for i in range(row_size) :
for j in range(col_size) :
if (depth[i][j] <= l) :
print("({}, {})".format(i,j),end='')
nc+=1
print(" ",nc)
(1, 0)(1, 1)(1, 2) 3
Complejidad de Tiempo: O(N * M) donde N es el número total de filas y M es el número total de columnas
Espacio Auxiliar: O(N * M)
Publicación traducida automáticamente
Artículo escrito por agnivakolay y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA