We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
classNode:def__init__(self,idx):self.idx=idxself.reacheables=[]defconnect(self,node):self.reacheables.append(node)classGraph:def__init__(self):self.nodes={}defconnect(self,node1_id,node2_id):ifnode1_idinself.nodes:node1=self.nodes[node1_id]else:node1=Node(node1_id)ifnode2_idinself.nodes:node2=self.nodes[node2_id]else:node2=Node(node2_id)node1.connect(node2)node2.connect(node1)self.nodes[node1_id]=node1self.nodes[node2_id]=node2deffind_distance(self,s,val):levels={s:0}frontier=[s]j=1whilefrontier:next_node=[]fornodeinfrontier:childs=node.reacheablesforchildinchilds:ifchild.idxnotinlevels:ifchild.idx==val:returnjlevels[child.idx]=jnext_node.append(child)j+=1frontier=next_nodereturn"Problem, seems not reached"defminimumMoves(grid,startX,startY,goalX,goalY):g=Graph()l=len(grid)# CREATE THE GRAPH:foriinrange(l):forjinrange(l):ifgrid[i][j]!='X':cell_id=(i,j)ifcell_iding.nodes:node_cell=g.nodes[cell_id]else:node_cell=Node(cell_id)g.nodes[cell_id]=node_cellifi<l-1:r_neighb=i+1whiler_neighb<landgrid[r_neighb][j]!='X':g.connect(cell_id,(r_neighb,j))r_neighb+=1ifj<l-1:l_neighb=j+1whilel_neighb<landgrid[i][l_neighb]!='X':g.connect(cell_id,(i,l_neighb))l_neighb+=1start_node=g.nodes[(startX,startY)]sol=g.find_distance(start_node,(goalX,goalY))returnsol
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Castle on the Grid
You are viewing a single comment's thread. Return to all comments →
Python 3 solution with a Graph and BFS.