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.<\/p>\n
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.<\/p>\n
See code below.<\/p>\n
<\/p>\n
Problem:\u00a0<\/strong>undirected graph and two distinct vertices u and v, check if there is a path between u and v.<\/p>\n Input Format:\u00a0<\/strong>An undirected graph with n vertices and m edges. The next line contains two vertices u and v of the graph.<\/p>\n Constraints:<\/strong>\u00a02 \u2264 n \u2264 10^3 ; 1 \u2264 m \u2264 10^3 ; 1 \u2264 u, v \u2264 n; u != v.<\/p>\n Result:\u00a0<\/strong>1 if path exists, 0 if no path exists.<\/p>\n <\/p>\n","protected":false},"excerpt":{"rendered":" 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, […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_crdt_document":"","footnotes":""},"categories":[3,4],"tags":[28,30],"series":[],"class_list":["post-163","post","type-post","status-publish","format-standard","hentry","category-python","category-code","tag-python","tag-code"],"_links":{"self":[{"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/posts\/163","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/comments?post=163"}],"version-history":[{"count":2,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/posts\/163\/revisions"}],"predecessor-version":[{"id":292,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/posts\/163\/revisions\/292"}],"wp:attachment":[{"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/media?parent=163"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/categories?post=163"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/tags?post=163"},{"taxonomy":"series","embeddable":true,"href":"https:\/\/eipsoftware.com\/musings\/wp-json\/wp\/v2\/series?post=163"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}#Uses python3\r\n\r\nimport sys\r\n\r\nclass UserGraph:\r\n def __init__(self):\r\n self.data = [] # data list from user\r\n self.edges = [] # convert data list into edges\r\n self.cc = [] #connected components\r\n self.cc_cnt = 0 #connected components count\r\n self.visited = [] # keep track if visited node before\r\n self.adj = [] # adjancency matrix\r\n\r\n def read(self):\r\n input = sys.stdin.read()\r\n self.data = list(map(int, input.split()))\r\n\r\n def explore(self,k_node):\r\n self.visited[k_node] = True\r\n self.cc[k_node] = self.cc_cnt\r\n for j in range(len(self.visited)):\r\n if self.adj[k_node][j] and not self.visited[j]:\r\n success = self.explore(j)\r\n\r\n def reach(self, x, y):\r\n self.explore(x-1)\r\n if self.cc[y-1] == 0:\r\n return 1\r\n else:\r\n return 0\r\n\r\n def process_input(self):\r\n n, m = self.data[0:2]\r\n self.data = self.data[2:]\r\n self.edges = list(zip(self.data[0:(2 * m):2], self.data[1:(2 * m):2]))\r\n x, y = self.data[2 * m:] # which nodes to see if connected\r\n self.adj = [[0] * n for _ in range(n)]\r\n self.visited = [False] * n # haven't visited any nodes\r\n self.cc = [-1] * n # nothing is connected\r\n return (x, y)\r\n\r\n def populate_adjacency_matrix(self):\r\n for (a, b) in self.edges:\r\n self.adj[a - 1][b-1] = 1\r\n self.adj[b - 1][a-1] = 1\r\n # print(self.adj)\r\n\r\n def node_reach(self):\r\n x_coord, y_coord = self.process_input()\r\n self.populate_adjacency_matrix()\r\n result = self.reach(x_coord, y_coord)\r\n return result\r\n\r\n\r\nif __name__ == '__main__':\r\n test_Graph = UserGraph()\r\n test_Graph.read()\r\n print(test_Graph.node_reach())<\/pre>\n