fork(6) download
copy 
  1. import java.util.LinkedList;
  2. import java.util.Queue;
  3.  
  4. /**
  5.  * Find the least number of hops between source and destination
  6.  * @author PRATEEK
  7.  */
  8. class KnightShortestPath {
  9.  
  10. 	private static final int BLANK = -1;
  11. 	private static int rowLen;
  12. 	private static int colLen;
  13. 	private int[][] board;
  14.  
  15. 	private static Queue<Coordinate> queue;
  16.  
  17. 	public static void main(String[] args) {
  18.  
  19. 		int[][] board = 
  20. 			  { { -1, -1, -1, -1, -1, -1, -1, -1 },
  21. 				{ -1, -1, -1, -1, -1, -1, -1, -1 },
  22. 				{ -1, -1, -1, -1, -1, -1, -1, -1 },
  23. 				{ -1, -1, -1, -1, -1, -1, -1, -1 },
  24.  
  25. 				{ -1, -1, -1, -1, -1, -1, -1, -1 },
  26. 				{ -1, -1, -1, -1, -1, -1, -1, -1 },
  27. 				{ -1, -1, -1, -1, -1, -1, -1, -1 },
  28. 				{ -1, -1, -1, -1, -1, -1, -1, -1 } };
  29.  
  30. 		rowLen = board.length;
  31. 		colLen = board[0].length;
  32. 	int hops=	path(board, 0, 0,rowLen -1 ,colLen -1 );
  33. System.out.println(hops + " Moves");
  34. 	}
  35.  
  36. 	/**
  37. 	 * BFS to find the minimum moves to reach the destination
  38. 	 * @return return number of hops if solution is availale else -1
  39. 	 */
  40. 	public static int path(int[][] board, int startRow, int startCol, int endRow, int endCol) {
  41. 		queue = new LinkedList<Coordinate>();
  42. 		queue.add(new Coordinate(startRow, startCol));
  43. 		queue.add(null);  //this acts a delimiter
  44. 		board[startRow][startCol] = 0;
  45. 		int hops=0;
  46.  
  47. 		while (!queue.isEmpty()) {
  48. 			Coordinate popedItem = queue.poll();
  49.  
  50. 			if (popedItem == null) {
  51. 				hops++;
  52. 				queue.offer(null);
  53. 				//System.out.println("======");
  54. 				continue;
  55. 			} 
  56.  
  57. 				int r = popedItem.row;
  58. 				int c = popedItem.col;
  59.  
  60. 				board[r][c] = hops;
  61.  
  62. 				//System.out.println(hops + " " + r + " " + c);
  63.  
  64. 				if(r==endRow && c==endCol)
  65. 				{
  66. 					printSol(board);
  67. 					return hops;
  68. 				}
  69.  
  70.  
  71. 				Coordinate[] points = validCoordinates(board, r, c);
  72.  
  73. 				for (Coordinate o : points) {
  74. 					if (o != null)
  75. 						queue.add(o);
  76. 				}
  77. 		}
  78. 		return -1;
  79. 	}
  80.  
  81. 	private static boolean isValid(int[][] board, int row, int col) {
  82. 		if (row >= 0 && row < colLen && col >= 0 && col < rowLen
  83. 				&& board[row][col] == BLANK)
  84. 			return true;
  85. 		return false;
  86. 	}
  87.  
  88. 	public static Coordinate[] validCoordinates(int[][] board, int row, int col) {
  89. 		Coordinate[] points = new Coordinate[8];
  90.  
  91. 		if (isValid(board, row + 2, col + 1))
  92. 			points[0] = new Coordinate(row + 2, col + 1);
  93.  
  94. 		if (isValid(board, row + 1, col + 2))
  95. 			points[1] = new Coordinate(row + 1, col + 2);
  96.  
  97. 		if (isValid(board, row - 1, col + 2))
  98. 			points[2] = new Coordinate(row - 1, col + 2);
  99.  
  100. 		if (isValid(board, row - 2, col + 1))
  101. 			points[3] = new Coordinate(row - 2, col + 1);
  102.  
  103. 		if (isValid(board, row - 2, col - 1))
  104. 			points[4] = new Coordinate(row - 2, col - 1);
  105.  
  106. 		if (isValid(board, row - 1, col - 2))
  107. 			points[5] = new Coordinate(row - 1, col - 2);
  108.  
  109. 		if (isValid(board, row + 1, col - 2))
  110. 			points[6] = new Coordinate(row + 1, col - 2);
  111.  
  112. 		if (isValid(board, row + 2, col - 1))
  113. 			points[7] = new Coordinate(row + 2, col - 1);
  114.  
  115. 		return points;
  116. 	}
  117.  
  118. 	private static void printSol(int[][] board) {
  119. 		for(int i=0;i<colLen;i++)
  120. 		{
  121. 			for(int j=0;j<rowLen;j++)
  122. 			{
  123. 				System.out.print(board[i][j]+ "   ");
  124. 			}
  125. 			System.out.println();
  126. 		}
  127. 	}
  128. }
  129.  
  130. class Coordinate implements Comparable<Coordinate> {
  131.  
  132. 	public int row;
  133. 	public int col;
  134. 	public int level;
  135.  
  136. 	public Coordinate() {
  137. 		row = 0;
  138. 		col = 0;
  139. 	}
  140.  
  141. 	public Coordinate(int row, int col) {
  142. 		this.row = row;
  143. 		this.col = col;
  144. 		this.level = level;
  145.  
  146. 	}
  147. 	@Override
  148. 	public int compareTo(Coordinate that) {
  149. 		return this.row - that.row - this.col - that.col;
  150. 	}
  151. }
Success #stdin #stdout 0.07s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0   3   2   3   2   3   4   5   
3   4   1   2   3   4   3   4   
2   1   4   3   2   3   4   5   
3   2   3   2   3   4   3   4   
2   3   2   3   4   3   4   5   
3   4   3   4   3   4   5   4   
4   3   4   3   4   5   4   5   
5   4   5   4   5   4   5   6   
6 Moves
https://ideone.com/nGJDko
Knight's Shortest Path
language:
Java (12.0.1)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!