Writing in the front

  • Full text of data structure and algorithm

Knight travel problem (horse board)

class HorseChessboard { private static int X; private static int Y; Private static Boolean visited[][]; private static Boolean visited[]; Private static Boolean finished; 0 public static void main(String[] args) {X=8; Y=8; int row = 1; int column = 1; int[][] chessboard = new int[X][Y]; visited = new boolean[X][Y]; traversalChessboard(chessboard, row - 1, column - 1, 1); for (int[] ints : chessboard) { System.out.println(Arrays.toString(ints)); }} /** * @param row the current row starts from 0 * @param column the current column starts from 0 * @param step the current step starts from 1 */ public static void traversalChessboard(int[][] chessboard, int row, int column, int step) { chessboard[row][column] = step; visited[row][column] = true; ArrayList< point > points = next(new point (column, row)); // Sort (points) by non-incrementing the likelihood of the next step of all points selections; // iterate points while (! Points.isempty ()) {Point Point = points.remove(0); if (! // traversalChessboard(chessboard, point.y, point. X, step + 1); // traversalChessboard(chessboard, point.y, point. //step < X * Y; // Step < X * Y; If (step < X * Y &&! finished) { chessboard[row][column] = 0; visited[row][column] = false; } else { finished = true; }} // Based on the current position, calculate what other positions you can go, Public static ArrayList<Point> next(Point curPoint) {ArrayList<Point> points = new ArrayList<>(); Point p = new Point(); If ((p.x = curPoint.x-2) >= 0 && (p.y = curPoint.y-1) >= 0) {point.add (new Point(p)); } if ((p.x = curPoint.x - 1) >= 0 && (p.y = curPoint.y - 2) >= 0) { points.add(new Point(p)); } if ((p.x = curPoint.x + 1) < X && (p.y = curPoint.y - 2) >= 0) { points.add(new Point(p)); } if ((p.x = curPoint.x + 2) < X && (p.y = curPoint.y - 1) >= 0) { points.add(new Point(p)); } if ((p.x = curPoint.x + 2) < X && (p.y = curPoint.y + 1) < Y) { points.add(new Point(p)); } if ((p.x = curPoint.x + 1) < X && (p.y = curPoint.y + 2) < Y) { points.add(new Point(p)); } if ((p.x = curPoint.x - 1) >= 0 && (p.y = curPoint.y + 2) < Y) { points.add(new Point(p)); } if ((p.x = curPoint.x - 2) >= 0 && (p.y = curPoint.y + 1) < Y) { points.add(new Point(p)); } return points; } // Non-decrement sort 1,2,2,2, 2,3,4,5 Can have equal numbers in increments // based on all of the next steps of the current step, Public static void sort(ArrayList<Point> points) {ArrayList<Point> points; Sort.sort ((o1, o2) -> next(o1).size() - next(o2).size()); }}Copy the code

conclusion

Chessboard [row][column] = step; chessboard[row][column] = step; visited[row][column] = true; , recursively try until all the possibilities at this point have been tried and then quit. Chessboard [row][column] = 0; chessboard[row][column] = 0; visited[row][column] = false;

Finished Indicates the finished flag bit. When the final step is complete, change the FINISHED flag bit. If there is no sign finished, assuming that this point, A, B two kinds of possibility, A is the right choice, this time to A, A normal after you come back, no finished said A completed task, still need to B, but B returned, because there is no save the correct results, A will clear the faults of the access point, Therefore, you need to modify the FINISHED bit to ensure that the correct path can be traced back to the beginning

Optimize, rewrite sort method, calculate the next possibility among these possibilities according to the possibility in this selection, combine the greedy algorithm idea, choose the possibility with less possibility in the next step to try first.