栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

蓝桥杯:走迷宫

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

蓝桥杯:走迷宫

目录

题目描述

输入描述

输出描述

输入输出样例

题目分析:(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 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+10 && 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);
    }
}

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/962210.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号