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.
publicstaticintminimumMoves(List<String>grid,intstartX,intstartY,intgoalX,intgoalY){// We will assume the grid is filled and not empty// 1. Create a character matrix representing the SQUARE grid.intgridSize=grid.size();char[][]charGrid=newchar[gridSize][gridSize];for(inti=0;i<gridSize;i++){for(intj=0;j<gridSize;j++){charGrid[i][j]=grid.get(i).charAt(j);}}// 2. Implement BFS w/ a Queue. Point objects will be used to track valid cells.Queue<Point>queue=newLinkedList<>();// Create a "steps" matrix representing the steps to get to a cell in the grid.int[][]steps=newint[gridSize][gridSize];// Keep track of cells visited to avoid adding them to the Queue.boolean[][]visited=newboolean[gridSize][gridSize];// Add the starting point to the queue to start BFS.queue.add(newPoint(startX,startY));visited[startX][startY]=true;while(!queue.isEmpty()){Pointcurrent=queue.poll();// 3. We can move in 4 directions: Up (0), Right (1), Down (2), and Left (3).// To represent these directions, refer to xMove and yMove.// We will be adding to our queue the cells of each valid step in each // direction of our current cell.for(inti=0;i<4;i++){// Used to explore the "adjacent" cells a certain valid distance from // the current cell in each valid direction. intdistance=1;// Check if the cell we are trying to "move" into is a valid cell.// A valid cell is a cell that is not an obstacle (X), and within bounds.while(isSafe(gridSize,current.x+xMove[i]*distance,current.y+yMove[i]*distance,charGrid)&&!visited[current.x+xMove[i]*distance][current.y+yMove[i]*distance]){// Record the Point coordinates to be added into the queue.intnextX=current.x+xMove[i]*distance;intnextY=current.y+yMove[i]*distance;visited[nextX][nextY]=true;queue.add(newPoint(nextX,nextY));// Keep track of the "steps" taken to get to a cell.steps[nextX][nextY]=steps[current.x][current.y]+1;// Case where the point "adjacent" to current is the goal.if(nextX==goalX&&nextY==goalY){System.out.println(steps[nextX][nextY]);returnsteps[nextX][nextY];}distance++;}}}// By default, return -1, indicating that the grid was not valid.return-1;}// Helper arrays used to define directions.// To move up (index 0): xMove is -1, yMove is 0.// To move right (index 1): xMove is 0, yMove is 1.// To move down (index 2): xMove is 1, yMove is 0.// To move left (index 3): xMove is 0, yMove is -1.privatestaticint[]xMove={-1,0,1,0};privatestaticint[]yMove={0,1,0,-1};// Private helper class to check if a step/move to a cell is valid in the grid.privatestaticbooleanisSafe(intgridSize,intx,inty,char[][]charGrid){return(x>=0&&y>=0&&x<gridSize&&y<gridSize&&charGrid[x][y]=='.');}}// Private helper class used to instantiate "Point" objects// A "Point" is used in the queue used to store valid moves from// a current "Point"classPoint{publicintx,y;publicPoint(intx,inty){this.x=x;this.y=y;}}
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 →