Problem Statement:
Given a Source and Destination , find the minimum number of moves required to move a knight from Source to Destination.
Download Source Code
Solution:
To find the minimum moves from Source to Destination, I have used the BFS ( Breadth First Search) technique, once the Destination is reached print the Solution
Please post your suggestions and comments.
Happy Coding !! :)
Given a Source and Destination , find the minimum number of moves required to move a knight from Source to Destination.
Fig: Movement of Knight from Source to Destination |
Solution:
To find the minimum moves from Source to Destination, I have used the BFS ( Breadth First Search) technique, once the Destination is reached print the Solution
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 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 | /** * BFS to find the minimum moves to reach the destination * @return return number of hops if solution is availale else -1 */ public static int path(int[][] board, int startRow, int startCol, int endRow, int endCol) { queue = new LinkedList<Coordinate>(); queue.add(new Coordinate(startRow, startCol)); queue.add(null); //this acts a delimiter board[startRow][startCol] = 0; int hops=0; while (!queue.isEmpty()) { Coordinate popedItem = queue.poll(); if (popedItem == null) { hops++; queue.offer(null); //System.out.println("======"); continue; } int r = popedItem.row; int c = popedItem.col; board[r][c] = hops; //System.out.println(hops + " " + r + " " + c); if(r==endRow && c==endCol) { printSol(board); return hops; } Coordinate[] points = validCoordinates(board, r, c); for (Coordinate o : points) { if (o != null) queue.add(o); } } return -1; } private static boolean isValid(int[][] board, int row, int col) { if (row >= 0 && row < colLen && col >= 0 && col < rowLen && board[row][col] == BLANK) return true; return false; } public static Coordinate[] validCoordinates(int[][] board, int row, int col) { Coordinate[] points = new Coordinate[8]; if (isValid(board, row + 2, col + 1)) points[0] = new Coordinate(row + 2, col + 1); if (isValid(board, row + 1, col + 2)) points[1] = new Coordinate(row + 1, col + 2); if (isValid(board, row - 1, col + 2)) points[2] = new Coordinate(row - 1, col + 2); if (isValid(board, row - 2, col + 1)) points[3] = new Coordinate(row - 2, col + 1); if (isValid(board, row - 2, col - 1)) points[4] = new Coordinate(row - 2, col - 1); if (isValid(board, row - 1, col - 2)) points[5] = new Coordinate(row - 1, col - 2); if (isValid(board, row + 1, col - 2)) points[6] = new Coordinate(row + 1, col - 2); if (isValid(board, row + 2, col - 1)) points[7] = new Coordinate(row + 2, col - 1); return points; } private static void printSol(int[][] board) { for(int i=0;i<colLen;i++) { for(int j=0;j<rowLen;j++) { System.out.print(board[i][j]+ " "); } System.out.println(); } } |
Please post your suggestions and comments.
Happy Coding !! :)
hermes
ReplyDeletecheap jordans
hermes
russell westbrook shoes
yeezy boost 350
timberland outlet
yeezy
air max 2017
curry 5
hermes belt