蓝桥杯：走迷宫_java蓝桥杯中关于迷宫的问题

目录

题目描述

输入描述

输出描述

输入输出样例

题目分析：（BFS）

AC代码（Java）： 

---

题目描述

给定一个N×M 的网格迷宫 G。G 的每个格子要么是道路，要么是障碍物（道路用 1 表示，障碍物用 0 表示）。

已知迷宫的入口位置为 (x1​,y1​)，出口位置为(x2​,y2​)。问从入口走到出口，最少要走多少个格子。

输入描述

输入第 1 行包含两个正整数 N,M分别表示迷宫的大小。

接下来输入一个N×M 的矩阵。若G(x,y) = 1 表示其为道路，否则表示其为障碍物。

最后一行输入四个整数x1​,y1​,x2​,y2​，表示入口的位置和出口的位置。

数据范围：1≤N,M≤100, 0≤G(x,y)≤1,  1≤x1,y1≤N, 1≤x2,y2≤N 

输出描述

输出仅一行，包含一个整数表示答案。

若无法从入口到出口，则输出 −1。

输入输出样例

输入 

5 5 
1 0 1 1 0
1 1 0 1 1 
0 1 0 1 1
1 1 1 1 1
1 0 0 0 1
1 1 5 5 

输出 

8

题目分析：（BFS）

         这种看题目，一般DFS用来搜索可行解，BFS搜索最优解。题目要我们算最短路径，那么我们用BFS(DFS也行，就是要额外处理，因为对DFS来说，100*100数据量大，容易超时)

        1.BFS搜索三要素嘛，(1)将起始点进入队列,(2)然后依次将可以行走的方向加入队列,(3)更新步数（因为BFS每次搜索其实都是在寻找最优解的道路，每一步搜索都是一个最优解的坐标）

        2.因为我们这个是数组，要将属性添加到队列里面来访问，那我们就创造一个节点，节点里面存放该点的坐标和步数（即第几步能走到这里）

        3.然后不断搜索，如果搜索到终点，那么就更新result（result初始化为-1），也就是如果搜索完成，都没有更新result的话，就肯定不能走到终点。

        4.我们最后直接输出result即可

        PS:我尝试了常规的DFS搜索，拿不满分，后面的测试用例数据大了会超时，所以还是用了BFS来做。

AC代码（Java）： 

import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改
 
//开一个节点，节点里面存放坐标信息和步数信息（步数存放最短几步可以走到终点）
class Node{
    int row;
    int col;
    //步数
    int step;
    public Node(int row,int col,int step) {
        this.row = row;
        this.col = col;
        this.step = step;
    }
}
public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        //在此输入您的代码...
        int N = scan.nextInt();
        int M = scan.nextInt();
        //迷宫
        int[][] map = new int[N][M];
        //拿到迷宫数据
        for(int i = 0;i<N;i++) {
            for(int j = 0;j<M;j++) {
                map[i][j] = scan.nextInt();
            }
        }
        //分别拿到起始坐标和终点坐标(因为题目是从第一行开始的，但是我们数组下标是从0开始，那么我们就让他-1，跟数组保持一致)
        int startRow = scan.nextInt()-1;
        int startCol = scan.nextInt()-1;
        int endRow = scan.nextInt()-1;
        int endCol = scan.nextInt()-1;
        scan.close();
        //创建初始坐标节点,步数为0
        Node node = new Node(startRow,startCol,0);
        //队列进行搜索 
        Queue<Node> queue = new LinkedList<>();
        queue.offer(node);
        int result = -1;
 
        //强行修改起始坐标为1(TMD,为什么起始点如果是0也能走到终点？)
        map[startRow][startCol] = 1;
 
        while(!queue.isEmpty()) {
          //取出节点类用来查找
            Node root = queue.poll();
            //判断是否达到终点
            if(root.row==endRow && root.col==endCol) {
                //能搜索到终点，直接结束循环
                result = root.step;
                break;
            }
          //该节点满足能够行走的条件（即为1）
            if(map[root.row][root.col] == 1) {
            //因为广搜能搜索到的一般都是最优解，所以我们直接步数++；
                root.step++;
                //走过该节点之后标记为已经走过(因为障碍物不可走，那么我们也将走过的路修改成障碍物就行)
                map[root.row][root.col] = 0;
                //其余节点依次入队,我按照顺时针来走(右下左上)
                if(root.col+1<M && map[root.row][root.col+1]==1) {
              //将可以走的方向放入队列
                    Node rootNode = new Node(root.row, root.col+1,root.step);
                    queue.offer(rootNode);
                }
                if(root.row+1<N && map[root.row+1][root.col]==1) {
                    Node rootNode = new Node(root.row+1, root.col,root.step);
                    queue.offer(rootNode);
                }
                if(root.col>0 && map[root.row][root.col-1]==1) {
                    Node rootNode = new Node(root.row, root.col-1,root.step);
                    queue.offer(rootNode);
                }
                if(root.row>0 && map[root.row-1][root.col]==1) {
                    Node rootNode = new Node(root.row-1, root.col,root.step);
                    queue.offer(rootNode);
                }
            }
        }
        System.out.println(result);
    }
}