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.

We don't necessarily need to build a graph. We can use a queue directly. Here is my Python solution:

fromcollectionsimportdequedefminimumMoves(grid,startX,startY,goalX,goalY):# Note: # X means vertical direction in problem description's diagram# Y means horizontal direction in problem descritions's diagram# This is different with our habit. # So I don't use the word left, right, up, or down in my code to avoid misleading nameslen_X=len(grid)len_Y=len(grid[0])visited=[]foriinrange(len_X):visited.append([False]*len_Y)queue=deque()# In the queue, each element is a tuple# Each tuple has 3 elements: x, y, and the number of moves from starting point to this locationqueue.append((startX,startY,0))visited[startX][startY]=Truewhilequeue:cur_x,cur_y,cur_d=queue.popleft()ifcur_x==goalXandcur_y==goalY:returncur_d#Add all potential moves toward smaller Xforxinrange(cur_x)[::-1]:ifgrid[x][cur_y]=='.'andnotvisited[x][cur_y]:queue.append((x,cur_y,cur_d+1))visited[x][cur_y]=Trueelifgrid[x][cur_y]=='X':break#Add all potential moves toward bigger Xforxinrange(cur_x,len_X):ifgrid[x][cur_y]=='.'andnotvisited[x][cur_y]:queue.append((x,cur_y,cur_d+1))visited[x][cur_y]=Trueelifgrid[x][cur_y]=='X':break#Add all potential moves toward smaller Yforyinrange(cur_y)[::-1]:ifgrid[cur_x][y]=='.'andnotvisited[cur_x][y]:queue.append((cur_x,y,cur_d+1))visited[cur_x][y]=Trueelifgrid[cur_x][y]=='X':break#Add all potential moves toward bigger Yforyinrange(cur_y,len_Y):ifgrid[cur_x][y]=='.'andnotvisited[cur_x][y]:queue.append((cur_x,y,cur_d+1))visited[cur_x][y]=Trueelifgrid[cur_x][y]=='X':breakreturn-1#Theflagwhenthegoalisnotreachable

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 →

We don't necessarily need to build a graph. We can use a queue directly. Here is my Python solution: