Finding an Exit from a Maze using undirected graphs.
We can think of a maze as a rectangular grid of cells with paths between adjacent cells. If we want to find if there is a path from a given cell to a given exit from the maze, where the exit is represented by a cell, you can represent the maze as an undirected graph.
The nodes of the graph are cells of the maze, and two nodes are connected an undirected edge if they are adjacent and there is no wall between them. Therefore we can surmise we just need to see if a path, series of edges connecting the nodes, to determine if the two nodes are connected.
See code below.
Problem: undirected graph and two distinct vertices u and v, check if there is a path between u and v.
Input Format: An undirected graph with n vertices and m edges. The next line contains two vertices u and v of the graph.
Constraints: 2 ≤ n ≤ 10^3 ; 1 ≤ m ≤ 10^3 ; 1 ≤ u, v ≤ n; u != v.
Result: 1 if path exists, 0 if no path exists.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#Uses python3 import sys class UserGraph: def __init__(self): self.data = [] # data list from user self.edges = [] # convert data list into edges self.cc = [] #connected components self.cc_cnt = 0 #connected components count self.visited = [] # keep track if visited node before self.adj = [] # adjancency matrix def read(self): input = sys.stdin.read() self.data = list(map(int, input.split())) def explore(self,k_node): self.visited[k_node] = True self.cc[k_node] = self.cc_cnt for j in range(len(self.visited)): if self.adj[k_node][j] and not self.visited[j]: success = self.explore(j) def reach(self, x, y): self.explore(x-1) if self.cc[y-1] == 0: return 1 else: return 0 def process_input(self): n, m = self.data[0:2] self.data = self.data[2:] self.edges = list(zip(self.data[0:(2 * m):2], self.data[1:(2 * m):2])) x, y = self.data[2 * m:] # which nodes to see if connected self.adj = [[0] * n for _ in range(n)] self.visited = [False] * n # haven't visited any nodes self.cc = [-1] * n # nothing is connected return (x, y) def populate_adjacency_matrix(self): for (a, b) in self.edges: self.adj[a - 1][b-1] = 1 self.adj[b - 1][a-1] = 1 # print(self.adj) def node_reach(self): x_coord, y_coord = self.process_input() self.populate_adjacency_matrix() result = self.reach(x_coord, y_coord) return result if __name__ == '__main__': test_Graph = UserGraph() test_Graph.read() print(test_Graph.node_reach()) |
Leave a Reply