博客

package com.potato.learning.leetcode.string;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _0605_Search {
    int[][] res;
    static int[][] arr = new int[][]{
            {0, 0, 0, 0, 0, 0, 0, 0},
            {0, 0, 0, 0, 1, 0, 0, 0},
            {0, 0, 0, 0, 1, 0, 0, 0},
            {0, 0, 0, 0, 1, 0, 0, 0},
            {0, 0, 0, 0, 0, 0, 0, 0}
    };
    static int[] s = new int[]{2, 2};
    static int[] e = new int[]{2, 6};
    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    List<Node> openList = new ArrayList<Node>();

    public static void main(String[] args) {
        new _0605_Search().excute(arr, s, e);
    }

    // 求出start到end的最短路径
    public void excute(int[][] arr, int[] start, int[] end) {
        init(arr);
        search(new Node(start, null));
    }

    private void search(Node parent) {
        int[] start = parent.p;
        int x = start[0];
        int y = start[1];
        // 找到他四周的节点
        for (int i = 0; i < 4; i++) {
            int nx = x + dirs[i][0];
            int ny = y + dirs[i][1];
            // 判断是否合理
            if (nx >= 0 && nx < arr.length && ny >= 0 && ny < arr[0].length && res[nx][ny] != 1) {
                // 加入list
                openList.add(new Node(new int[]{nx, ny}, parent));
            }
        }
        // 计算list中，h值最小的那个，取出来
        if (openList.size() == 0) {
            return;
        }
        Node min = findMinh();
        // 查验是否到了终点
        if (isEnd(min)) {
            System.out.println(min);
            return;
        } else {
            res[min.p[0]][min.p[1]] = 1;
            openList.remove(min);
        }
        // 重复计算
        search(min);


    }

    private Node findMinh() {
        Node min = new Node(s, null);
        min.h = Integer.MAX_VALUE;
        for (Node open : openList) {
            if (open.h < min.h) {
                min = open;
            }
        }
        return min;
    }

    private boolean isEnd(Node node) {
        int[] p = node.p;
        if (p[0] == e[0] && p[1] == e[1]) {
            return true;
        }
        return false;
    }

    // 初始化一个一模一样的数组
    private void init(int[][] arr) {
        int[][] res = new int[arr.length][arr[0].length];
        for (int i = 0; i < arr.length; i++) {
            Arrays.fill(res[i], 0);
        }
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr[0].length; j++) {
                if (arr[i][j] == 1) {
                    res[i][j] = 1;
                }
            }
        }
        res[s[0]][s[1]] = 1;
        this.res = res;
    }

    static class Node {
        int f; // total
        int g; // used
        int h; // remain
        Node parent;
        int[] p;

        public Node(int[] p, Node parent) {
            this.parent = parent;
            this.g = this.parent == null ? 0 : this.parent.g + 1;
            this.h = Math.abs(p[0] - e[0]) + Math.abs(p[1] - e[1]);
            this.f = g + h;
            this.p = p;
        }
    }
}