Dados dos números enteros N y M , la tarea es generar cualquier laberinto de tamaño N * M que contenga solo 0 (que representa una pared) y 1 (que representa un espacio vacío donde uno puede moverse) con el punto de entrada como P0 y el punto de salida P1 y allí es sólo un camino entre dos posiciones móviles cualesquiera.
Nota: P0 y P1 estarán marcados como 2 y 3 respectivamente y uno puede moverse a través de las posiciones móviles en 4 direcciones (arriba, abajo, derecha e izquierda).
Ejemplos:
Entrada: N = 5, M = 5, P0 = (0, 0), P1 = (4, 4)
Salida: laberinto = [ [ 2 1 1 1 1 ],
[ 1 0 1 0 1 ],
[ 1 0 1 0 0 ],
[ 1 1 0 1 0 ],
[ 0 1 1 1 3 ] ]
Explicación: Es válido porque no hay ciclo,
y no hay posición transitable inalcanzable.
Algunas otras opciones podrían ser
[ [ 2 1 1 1 1 ],
[ 1 0 1 0 1 ],
[ 1 0 1 0 0 ],
[ 1 1 1 1 0 ],
[ 0 0 0 1 3 ] ]
o
[ [ 2 1 1 0 1 ],
[ 1 0 1 0 1 ],
[ 1 0 1 0 0 ],
[ 1 0 1 1 0 ],
[ 1 0 0 1 3 ] ].
Pero estos no son válidos porque en el primero hay un ciclo en el laberinto
y en el segundo (0, 4) y (1, 4) no se puede llegar desde el punto de partida.
Planteamiento: El problema se puede resolver a partir de la siguiente idea:
Use un DFS que comience desde la posición P0 y se mueva a cualquiera de los vecinos pero no haga un ciclo y termine en P1. De esta manera, solo habrá 1 camino entre dos posiciones móviles cualesquiera.
Siga los siguientes pasos para implementar la idea:
- Inicialice una pila (S) para el DFS iterativo , la array que se devolverá como el laberinto aleatorio.
- Inserte el punto de entrada P0 en la pila.
- Mientras S no esté vacío, repita los siguientes pasos:
- Elimine una posición (digamos P ) de S y márquela como se ve.
- Si marca la posición transitable, forma un ciclo, entonces no la incluya como una posición móvil.
- De lo contrario, establezca la posición como transitable.
- Inserte los vecinos de P que no son visitados en orden aleatorio en la pila.
- La inserción aleatoria en la pila garantiza que el laberinto que se genera es aleatorio.
- Si alguno de los vecinos es el mismo que el P1 , insértelo en la parte superior para que no saltemos esta posición debido a la formación del ciclo.
- Elimine una posición (digamos P ) de S y márquela como se ve.
- Marque la posición inicial P0 (con 2) y la posición final P1 (con 3)
- Devuelve el laberinto.
A continuación se muestra la implementación del enfoque anterior:
Python3
# Python3 code to implement the approach from random import randint # Class to define structure of a node class Node: def __init__(self, value = None, next_element = None): self.val = value self.next = next_element # Class to implement a stack class stack: # Constructor def __init__(self): self.head = None self.length = 0 # Put an item on the top of the stack def insert(self, data): self.head = Node(data, self.head) self.length += 1 # Return the top position of the stack def pop(self): if self.length == 0: return None else: returned = self.head.val self.head = self.head.next self.length -= 1 return returned # Return False if the stack is empty # and true otherwise def not_empty(self): return bool(self.length) # Return the top position of the stack def top(self): return self.head.val # Function to generate the random maze def random_maze_generator(r, c, P0, Pf): ROWS, COLS = r, c # Array with only walls (where paths will # be created) maze = list(list(0 for _ in range(COLS)) for _ in range(ROWS)) # Auxiliary matrices to avoid cycles seen = list(list(False for _ in range(COLS)) for _ in range(ROWS)) previous = list(list((-1, -1) for _ in range(COLS)) for _ in range(ROWS)) S = stack() # Insert initial position S.insert(P0) # Keep walking on the graph using dfs # until we have no more paths to traverse # (create) while S.not_empty(): # Remove the position of the Stack # and mark it as seen x, y = S.pop() seen[x][y] = True # Check if it will create a cycle # if the adjacent position is valid # (is in the maze) and the position # is not already marked as a path # (was traversed during the dfs) and # this position is not the one before it # in the dfs path it means that # the current position must not be marked. # This is to avoid cycles with adj positions if (x + 1 < ROWS) and maze[x + 1][y] == 1 \ and previous[x][y] != (x + 1, y): continue if (0 < x) and maze[x-1][y] == 1 \ and previous[x][y] != (x-1, y): continue if (y + 1 < COLS) and maze[x][y + 1] == 1 \ and previous[x][y] != (x, y + 1): continue if (y > 0) and maze[x][y-1] == 1 \ and previous[x][y] != (x, y-1): continue # Mark as walkable position maze[x][y] = 1 # Array to shuffle neighbours before # insertion to_stack = [] # Before inserting any position, # check if it is in the boundaries of # the maze # and if it were seen (to avoid cycles) # If adj position is valid and was not seen yet if (x + 1 < ROWS) and seen[x + 1][y] == False: # Mark the adj position as seen seen[x + 1][y] = True # Memorize the position to insert the # position in the stack to_stack.append((x + 1, y)) # Memorize the current position as its # previous position on the path previous[x + 1][y] = (x, y) if (0 < x) and seen[x-1][y] == False: # Mark the adj position as seen seen[x-1][y] = True # Memorize the position to insert the # position in the stack to_stack.append((x-1, y)) # Memorize the current position as its # previous position on the path previous[x-1][y] = (x, y) if (y + 1 < COLS) and seen[x][y + 1] == False: # Mark the adj position as seen seen[x][y + 1] = True # Memorize the position to insert the # position in the stack to_stack.append((x, y + 1)) # Memorize the current position as its # previous position on the path previous[x][y + 1] = (x, y) if (y > 0) and seen[x][y-1] == False: # Mark the adj position as seen seen[x][y-1] = True # Memorize the position to insert the # position in the stack to_stack.append((x, y-1)) # Memorize the current position as its # previous position on the path previous[x][y-1] = (x, y) # Indicates if Pf is a neighbour position pf_flag = False while len(to_stack): # Remove random position neighbour = to_stack.pop(randint(0, len(to_stack)-1)) # Is the final position, # remember that by marking the flag if neighbour == Pf: pf_flag = True # Put on the top of the stack else: S.insert(neighbour) # This way, Pf will be on the top if pf_flag: S.insert(Pf) # Mark the initial position x0, y0 = P0 xf, yf = Pf maze[x0][y0] = 2 maze[xf][yf] = 3 # Return maze formed by the traversed path return maze # Driver code if __name__ == "__main__": N = 5 M = 5 P0 = (0, 0) P1 = (4, 4) maze = random_maze_generator(N, M, P0, P1) for line in maze: print(line)
[2, 0, 0, 1, 1] [1, 1, 1, 0, 1] [0, 0, 1, 1, 1] [1, 1, 0, 0, 1] [0, 1, 1, 1, 3]
Complejidad de tiempo: O(N * M)
- Como el algoritmo es básicamente un DFS con más condiciones, la complejidad temporal es la complejidad temporal del DFS: O(V+E) (donde V es el número de vértices y E es el número de aristas).
- En este caso, el número de vértices es el número de cuadrados en la array: N * M. Cada «vértice» (cuadrado) tiene como máximo 4 «aristas» (4 cuadrados adyacentes), por lo que E < 4*N*M. Entonces O(V+E) será O(5*N*M), es decir, O(N*M).
Espacio Auxiliar: O(N * M)
- Cada array auxiliar necesita O(N*M) de espacio.
- La pila no puede tener más de N*M cuadrados dentro, porque nunca contiene (en esta implementación) el mismo cuadrado más de una vez.
- La suma de todos los espacios mencionados será O(N*M).