题解 | #迷宫问题#---给刘思光的答案1之广度优先搜索

package m6_18;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class migongzuiduan {
    private static int[][] viseted;
    private static int[][] mize;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int rowlen = in.nextInt();
        int collen = in.nextInt();
        mize = new int[rowlen][collen];
        for (int i = 0; i < rowlen; i++) {
            for (int j = 0; j < collen; j++) {
                mize[i][j] = in.nextInt();
            }
        }
        viseted = new int[rowlen][collen];
        List<int[]> line = new ArrayList<>(); //广度优先搜索路径节点信息
        List<int[]> queue = new ArrayList<>(); //广度搜索队列工具
        int[] start = {0, 0};
        int[] end = {rowlen - 1, collen - 1};
        queue.add(start);
        viseted[0][0] = 1;
        //判断4个方向是否可以行走，如果可行，则记入队列
        while (line.isEmpty() || !((line.get(line.size() - 1)[0] == end[0]) && (line.get(line.size() - 1)[1] == end[1]))) {
            if (isway(1, queue.get(0))) {            //1.2.3.4为方向 上下左右
                queue.add(new int[]{queue.get(0)[0] - 1, queue.get(0)[1]});
                viseted[queue.get(0)[0] - 1][queue.get(0)[1]] = 1;
            }
            if (isway(2, queue.get(0))) {
                queue.add(new int[]{queue.get(0)[0] + 1, queue.get(0)[1]});
                viseted[queue.get(0)[0] + 1][queue.get(0)[1]] = 1;
            }
            if (isway(3, queue.get(0))) {
                queue.add(new int[]{queue.get(0)[0], queue.get(0)[1] - 1});
                viseted[queue.get(0)[0]][queue.get(0)[1] - 1] = 1;
            }
            if (isway(4, queue.get(0))) {
                queue.add(new int[]{queue.get(0)[0], queue.get(0)[1] + 1});
                viseted[queue.get(0)[0]][queue.get(0)[1] + 1] = 1;
            }
            line.add(queue.get(0));
            queue.remove(0);
        }

        List<int[]> result = new ArrayList<>();
        result.add(end);
        // 在路径节点信息队列中，从后往前推，寻找最短路径，记入result队列中
        while (!((result.get(result.size() - 1)[0] == start[0]) && (result.get(result.size() - 1)[1] == start[1]))) {
            for (int i = 0; i < line.size(); i++) {
                if (isNeighbor(result, line.get(i))) {
                    result.add(line.get(i));
                    break;
                }
            }
        }
        System.out.println("最短路径之一为：");
        for (int i = result.size() - 1; i >= 0; i--) {
            System.out.println("(" + result.get(i)[0] + "," + result.get(i)[1] + ")");
        }
    }
    //判断两点是否是相邻的
    private static boolean isNeighbor(List<int[]> result, int[] ints) {
        int[] loc = result.get(result.size() - 1);
        if ((Math.abs(loc[0] - ints[0]) + Math.abs(loc[1] - ints[1])) < 2) {
            return true;
        }
        return false;
    }
    //判断direct方向上是否可行
    private static boolean isway(int direct, int[] loc) {
        switch (direct) {
            case 1:
                if (loc[0] > 0 && viseted[loc[0] - 1][loc[1]] == 0 && mize[loc[0] - 1][loc[1]] == 0) return true;
                break;
            case 2:
                if (loc[0] < mize.length - 1 && viseted[loc[0] + 1][loc[1]] == 0 && mize[loc[0] + 1][loc[1]] == 0)
                    return true;
                break;
            case 3:
                if (loc[1] > 0 && viseted[loc[0]][loc[1] - 1] == 0 && mize[loc[0]][loc[1] - 1] == 0) return true;
                break;
            case 4:
                if (loc[1] < mize[0].length - 1 && viseted[loc[0]][loc[1] + 1] == 0 && mize[loc[0]][loc[1] + 1] == 0)
                    return true;
                break;
        }
        return false;
    }
}