当前位置: 首页 > article >正文

1216走迷宫

1216走迷宫

⭐️难度:简单
🌟考点:bfs
📖
在这里插入图片描述

📚

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int m = sc.nextInt();
        int [][] a = new int [n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        int x1 = sc.nextInt();
        int y1 = sc.nextInt();
        int x2 = sc.nextInt();
        int y2 = sc.nextInt();

        boolean [][] v = new boolean[n+2][m+2];// 是否被访问
        int [][] d = new int[n+1][m+1]; // 起点到各个点的距离
        for (int i = 1; i <= n; i++) {
            Arrays.fill(d[i],(int)1e9); // 先全部设为无限大,不可到达
        }
        Queue<int[]> q = new LinkedList<>(); // 队列记录即将遍历的结点

        // bfs
        d[x1][y1] = 0;
        q.add(new int[]{x1,y1});
        int[] dx = {0,0,1,-1}; // 分别对应:右左上下 四个操作
        int[] dy = {1,-1,0,0};
        while(!q.isEmpty()){
            int []xy = q.poll();
            int x = xy[0];
            int y = xy[1];
            if(v[x][y]) continue; // 已经被访问过了
            v[x][y] = true;
            for(int i = 0;i < 4;i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx > n || nx < 1 || ny > m || ny < 1 || a[nx][ny] == 0 || v[nx][ny]) continue; // 该点不合法:超出范围或不可访问或已被访问
                q.add(new int[]{nx,ny});
                d[nx][ny] = d[x][y] + 1; // 在原来的步数上+1,就走到了当前这个结点
            }
        }
        if(!v[x2][y2]){ // 没有被访问,不可到达
            System.out.println("-1");
        }else{
            System.out.println(d[x2][y2]);
        }
    }
}

细节:Boolean和boolean不一样,Boolean不会初始化为false,会报空指针异常。


http://www.kler.cn/a/587077.html

相关文章:

  • Keil5下载教程及安装教程(附安装包)
  • Unity AssetBundles资源加载管理器
  • Debain-12.9使用xinference部署音频模型/audio
  • 《灵珠觉醒:从零到算法金仙的C++修炼》卷三·天劫试炼(48)戮魂幡染节点 - 二分图检测(着色法)
  • 【NLP】 9. 处理创造性词汇 词组特征(Creative Words Features Model), 词袋模型处理未知词,模型得分
  • 【黑马点评|项目】万字总结(下)
  • Python软件和搭建运行环境
  • C++进阶——map和set的使用
  • Python在数据处理中的应用:从入门到精通
  • Linux date 命令使用指南
  • 用Python打造AI玩家:挑战2048,谁与争锋
  • Socket服务器和客户端
  • 安装SQL数据库并且在jupyter中连接,运行
  • 回溯法--力扣第17题“电话号码的字母组合”(java)
  • 【初级篇】如何使用DeepSeek和Dify构建高效的企业级智能客服系统
  • stable Diffusion 中的 VAE是什么
  • Maximize Rating
  • [动手学习深度学习]24. AlexNet
  • 神经网络的基本知识
  • 补充二分LIS