Day600.马踏棋盘算法 -数据结构和算法Java

马踏棋盘算法

• 图的深度优先DFS
• 回溯
• 八皇后问题、小老鼠找迷宫问题

一、介绍

二、思路分析

三、代码实现

package com.achang.algorithm;

import java.awt.*;
import java.util.ArrayList;

/**
 * 马踏棋盘问题&骑士周游问题
 */
public class Horse {
    public static void main(String[] args) {

    }

}

/**
 * 棋盘
 */
class HorseChessBoard {
    private static int x;//棋盘的列数
    private static int y;//棋盘的行数

    /**
     * 获取当前节点接下来能走哪个点
     *
     * @param curPoint 当前点
     * @return 接下来可以走的点
     */
    public static ArrayList<Point> next(Point curPoint) {
        ArrayList<Point> points = new ArrayList<>();
        Point point = new Point();
        //表示马可以走5这个位置
        if ((point.x = curPoint.x - 2) >= 0 && (point.y = point.y - 1) >= 0) {
            points.add(new Point(point));
        }
        //表示马可以走6这个位置
        if ((point.x = curPoint.x - 1) >= 0 && (point.y = point.y - 2) >= 0) {
            points.add(new Point(point));
        }
        //表示马可以走7这个位置
        if ((point.x = curPoint.x + 1) < x && (point.y = point.y - 2) >= 0) {
            points.add(new Point(point));
        }
        //表示马可以走0这个位置
        if ((point.x = curPoint.x + 2) < x && (point.y = point.y - 1) >= 0) {
            points.add(new Point(point));
        }
        //表示马可以走1这个位置
        if ((point.x = curPoint.x + 2) < x && (point.y = point.y + 1) < y) {
            points.add(new Point(point));
        }
        //表示马可以走2这个位置
        if ((point.x = curPoint.x + 1) < x && (point.y = point.y + 2) < y) {
            points.add(new Point(point));
        }
        //表示马可以走3这个位置
        if ((point.x = curPoint.x - 1) >= 0 && (point.y = point.y + 2) < y) {
            points.add(new Point(point));
        }
        //表示马可以走4这个位置
        if ((point.x = curPoint.x - 2) >= 0 && (point.y = point.y + 1) < y) {
            points.add(new Point(point));
        }
        return points;
    }
}

写了一半，明天继续

四、贪心算法优化方案