您现在的位置是:首页 > 后台技术 > 数据结构与算法数据结构与算法
马踏棋盘(图文)
第十三双眼睛2023-10-24【数据结构与算法】人已围观
简介马踏棋盘
马踏棋盘
用贪心算法改造:
package com.xingchen.day017; import java.awt.*; import java.util.ArrayList; import java.util.List; public class HorseChessBoard { private static int X ;//表示棋盘的列 private static int Y ; //表示棋盘的行 // 创建一个数组来标记棋盘的各个位置是否被访问过 private static boolean[] visited; //使用一个属性,标记棋盘的所有位置是否都被访问过 private static boolean finish; public static void main(String[] args) { X = 6; Y = 6; int row = 1; int column = 1; //创建棋盘 int[][] chessBoard = new int[X][Y]; visited = new boolean[X * Y]; travel(chessBoard, row - 1, column -1 ,1); for (int[] rowss: chessBoard) { for (int col : rowss) { System.out.print(col+" "); } System.out.println(""); } } /** * * @param chessBorard 棋盘 * @param row 行 * @param column 列 * @param step 步数 */ public static void travel(int[][] chessBorard,int row, int column, int step) { chessBorard[row][column] = step; visited[row * X + column] = true; //获取可以走的下一个位置 List<Point> ps = next(new Point(column, row)); while (!ps.isEmpty()) { Point p = ps.remove(0); //判断该店是否已经访问过了 if (!visited[p.y * X + p.x]) { travel(chessBorard, p.y,p.x, step + 1); } } if (step < X * Y && !finish) { chessBorard[row][column] = 0; visited[row * X + column] = false; } else { finish = true; } } //根据当前位置,计算还能访问哪些位置 public static List<Point> next(Point current) { List<Point> ps = new ArrayList<>(); Point p1 = new Point(); //5 if ((p1.x = current.x - 2) >= 0 && (p1.y = current.y - 1) >= 0) { ps.add(new Point(p1)); } //6 if ((p1.x = current.x - 1) >= 0 && (p1.y = current.y - 2) >= 0) { ps.add(new Point(p1)); } //7 if ((p1.x = current.x + 1) < X && (p1.y = current.y - 2) >= 0) { ps.add(new Point(p1)); } //0 if ((p1.x = current.x + 2) < X && (p1.y = current.y - 1) >= 0) { ps.add(new Point(p1)); } //1 if ((p1.x = current.x + 2) < X && (p1.y = current.y + 1) < Y) { ps.add(new Point(p1)); } //2 if ((p1.x = current.x + 1) < X && (p1.y = current.y + 2) < Y) { ps.add(new Point(p1)); } //3 if ((p1.x = current.x - 1) >= 0 && (p1.y = current.y + 2) < Y) { ps.add(new Point(p1)); } //4 if ((p1.x = current.x - 2) >= 0 && (p1.y = current.y + 1) < Y) { ps.add(new Point(p1)); } return ps; } } |
用贪心算法改造:
package com.xingchen.day017; import java.awt.*; import java.util.ArrayList; import java.util.Comparator; import java.util.List; public class HorseChessBoard { private static int X ;//表示棋盘的列 private static int Y ; //表示棋盘的行 // 创建一个数组来标记棋盘的各个位置是否被访问过 private static boolean[] visited; //使用一个属性,标记棋盘的所有位置是否都被访问过 private static boolean finish; 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]; travel(chessBoard, row - 1, column -1 ,1); for (int[] rowss: chessBoard) { for (int col : rowss) { System.out.print(col+" "); } System.out.println(""); } } /** * * @param chessBorard 棋盘 * @param row 行 * @param column 列 * @param step 步数 */ public static void travel(int[][] chessBorard,int row, int column, int step) { chessBorard[row][column] = step; visited[row * X + column] = true; //获取可以走的下一个位置 List<Point> ps = next(new Point(column, row)); //对ps进行排序 ssort(ps); while (!ps.isEmpty()) { Point p = ps.remove(0); //判断该店是否已经访问过了 if (!visited[p.y * X + p.x]) { travel(chessBorard, p.y,p.x, step + 1); } } if (step < X * Y && !finish) { chessBorard[row][column] = 0; visited[row * X + column] = false; } else { finish = true; } } //根据当前位置,计算还能访问哪些位置 public static List<Point> next(Point current) { List<Point> ps = new ArrayList<>(); Point p1 = new Point(); //5 if ((p1.x = current.x - 2) >= 0 && (p1.y = current.y - 1) >= 0) { ps.add(new Point(p1)); } //6 if ((p1.x = current.x - 1) >= 0 && (p1.y = current.y - 2) >= 0) { ps.add(new Point(p1)); } //7 if ((p1.x = current.x + 1) < X && (p1.y = current.y - 2) >= 0) { ps.add(new Point(p1)); } //0 if ((p1.x = current.x + 2) < X && (p1.y = current.y - 1) >= 0) { ps.add(new Point(p1)); } //1 if ((p1.x = current.x + 2) < X && (p1.y = current.y + 1) < Y) { ps.add(new Point(p1)); } //2 if ((p1.x = current.x + 1) < X && (p1.y = current.y + 2) < Y) { ps.add(new Point(p1)); } //3 if ((p1.x = current.x - 1) >= 0 && (p1.y = current.y + 2) < Y) { ps.add(new Point(p1)); } //4 if ((p1.x = current.x - 2) >= 0 && (p1.y = current.y + 1) < Y) { ps.add(new Point(p1)); } return ps; } public static void ssort(List<Point> ps) { ps.sort(new Comparator<Point>() { @Override public int compare(Point o1, Point o2) { int c1 = next(o1).size(); int c2 = next(o2).size(); if (c1 < c2) { return -1; } else if (c1== c2) { return 0; } return 1; } }); } } |
Tags:
很赞哦! ()
上一篇:弗洛伊德算法(图文)
下一篇:两数之和