算法:迷宫问题
描述
定义一个二维数组 N*M ,如 5 × 5 数组下所示:
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的路线。入口点为[0,0],既第一格是可以走的路。数据范围: 2≤n,m≤10 , 输入的内容只包含 0≤val≤1
输入描述:
输入两个整数,分别表示二维数组的行数,列数。再输入相应的数组,其中的1表示墙壁,0表示可以走的路。数据保证有唯一解,不考虑有多解的情况,即迷宫只有一条通道。
输出描述:
左上角到右下角的最短路径,格式如样例所示。
示例1
输入:
5 5 0 1 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0输出:
(0,0) (1,0) (2,0) (2,1) (2,2) (2,3) (2,4) (3,4) (4,4)示例2
输入:
5 5 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0输出:
(0,0) (1,0) (2,0) (3,0) (4,0) (4,1) (4,2) (4,3) (4,4)说明:
注意:不能斜着走!!
import java.util.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextInt()) { // 注意 while 处理多个 caseint a = in.nextInt();int b = in.nextInt();int[][] array = new int[a][b];for (int i=0; i<a; i++) {for (int j=0; j<b; j++) {array[i][j] = in.nextInt();}}getRes1(array);}}public static void getRes1(int[][] array) {int dS = array.length;int rS = array[0].length;int[][] res = new int[dS][rS];Obj [][] objs = new Obj[dS][rS];Obj start = Obj.build(0, 0);start.before = null;objs[0][0] = start;// 消息队列Queue<Obj> queue = new LinkedList<>();queue.add(start);int[] chooses = {0, 1, 2, 3};while (!queue.isEmpty()) {Obj obj = queue.poll();// 已经存在数据的元素不允许被覆盖if (objs[obj.d][obj.r] == null) {objs[obj.d][obj.r] = obj.before;}if (obj.equals(dS-1, rS-1)) {break;}for (int i=0; i<chooses.length; i++) {switch(i) {case 0:if (obj.r+1<rS && array[obj.d][obj.r+1]==0) {Obj tmp = Obj.build(obj.d, obj.r+1);tmp.before = obj;queue.add(tmp);}break;case 1:if (obj.d+1<dS && array[obj.d+1][obj.r]==0) {Obj tmp = Obj.build(obj.d+1, obj.r);tmp.before = obj;queue.add(tmp);}break;case 2:if (obj.r-1>=0 && array[obj.d][obj.r-1]==0) {Obj tmp = Obj.build(obj.d, obj.r-1);tmp.before = obj;queue.add(tmp);}break;case 3:if (obj.d-1>=0 && array[obj.d-1][obj.r]==0) {Obj tmp = Obj.build(obj.d-1, obj.r);tmp.before = obj;queue.add(tmp);}break;}}}String s = "";if (objs[dS-1][rS-1] != null) {int i=dS-1, j=rS-1;s = "("+i+","+j+")\n";boolean bool = true;while (bool) {int d=objs[i][j].d;int r=objs[i][j].r;s = "("+d+","+r+")\n" + s;if ((d==0 && r==0)) {bool = false;}else {i = d;j = r;}}// s = "("+0+","+0+")\n"+s;System.out.println(s);}}public static class Obj {int d;int r;Obj before;public static Obj build(int d, int r) {Obj o = new Obj();o.d = d;o.r = r;return o;}public boolean equals(int d, int r) {return this.d==d && this.r==r;}}
}

// 已经存在数据的元素不允许被覆盖,顺序应该是由下往上
if (objs[obj.d][obj.r] == null) {
objs[obj.d][obj.r] = obj.before;
}
相关文章:
算法:迷宫问题
描述 定义一个二维数组 N*M ,如 5 5 数组下所示: int maze[5][5] { 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, }; 它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或…...
聊聊并发编程的12种业务场景
前言 并发编程是一项非常重要的技术,无论在面试,还是工作中出现的频率非常高。 并发编程说白了就是多线程编程,但多线程一定比单线程效率更高? 答:不一定,要看具体业务场景。 毕竟如果使用了多线程&…...
MySQL执行顺序
MySQL执行顺序 MySQL语句的执行顺序也是在面试过程中经常问到的问题,并且熟悉执行顺序也有助于SQL语句的编写。 SELECT FROM JOIN ON WHERE GROUP BY HAVING ORDER BY LIMIT执行顺序如下: FROM ON JOIN WHERE GROUP BY # (开始使用别名) SUM # SUM等…...
引领真无线耳机未来趋势,NANK南卡OE骨传导真无线耳机惊艳亮相
传统的蓝牙耳机存在很多问题,例如续航时间短、长期佩戴耳朵会不舒服,甚至影响听力等等。为了解决这些问题,在骨传导领域深耕十多年的南卡品牌推出了这款真无线骨传导耳机——NANK南卡 OE。 NANK南卡OE即将正式上线,这一消息一经宣…...
5款写作神器,帮助你写出5w+爆款文案,好用到哭
我不允许还有文案小白、新手博主不知道这5款写作利器! 每次一写文案就头秃的新媒体工作者,赶紧看过来吧!这5款好用到爆的写作神器,喝一杯咖啡的时间就能完成写作。 我和同事都是用它们,出了很多的爆款,现…...
相交链表问题
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。 图示两个链表在节点 c1 开始相交: 题目数据 保证 整个链式结构中不存在环。 注意,函数返回结果后&…...
[ubuntu] ax200网卡虚接,导致系统根目录占满而无法进入系统的奇葩问题
20230508,我像往常一样,打开电脑发现根目录满了,报警了,所以按照网上的教程,清理了一下根目录的文件,没想到背后是网卡问题… 文章目录 1.进入终端模式2.查看占用情况3.清理系统log文件3.1 清理/var/log/syslog3.2 清…...
本地字体库的引入方法
本地字体库是指在计算机系统中存储的一组字体文件,通常包含多种字体格式,如TTF、OTF、WOFF等。引入本地字体库可以让用户在使用计算机时可以选择不同的字体,从而提高用户的使用体验。 本地字体库的引入方式有多种,其中比较常用的是…...
7种优秀的导航菜单设计总结
导航是应用程序界面中最常见的模块之一,在链接应用程序中起着每个页面的作用。 不同的设计需求和业务目标决定了导航的设计因品而异,移动设备的尺寸远小于计算机。因此,在设计移动终端导航时,应考虑更全面,以确保简单…...
Problem E. 矩阵游戏 (2023年ccpc河南省赛)
原题链接: https://codeforces.com/gym/104354 题意: 有一个n*m的矩阵,只有三种字符:0,1和?。从[1,1]走到[n,m],每次只能向下走或者向下走。当走到1的时候得一分,走到0的时候不得分,走到?的时候可以将他…...
数字孪生模型构建理论及应用
源自:计算机集成制造系统 作者:陶飞 张贺 戚庆林 徐 俊 孙铮 胡天亮 刘晓军 刘庭煜 关俊涛 陈畅宇 孟凡伟 张辰源 李志远 魏永利 朱铭浩 肖斌 摘 要 数字孪生作为实现数字化转型和促进智能化升级的重要使能途径,一直备受各…...
Vue面试题:30道含答案和代码示例的练习题
Vue中的双向数据绑定是怎么实现的? 双向数据绑定通过使用v-model指令实现。v-model指令会在表单元素上创建一个监听器,在用户输入时实时更新Vue实例的数据,并且在Vue实例数据变化时更新表单元素的值。 如何在Vue中定义一个方法?…...
2023-05-09 LeetCode每日一题(有效时间的数目)
2023-05-09每日一题 一、题目编号 2437. 有效时间的数目二、题目链接 点击跳转到题目位置 三、题目描述 给你一个长度为 5 的字符串 time ,表示一个电子时钟当前的时间,格式为 “hh:mm” 。最早 可能的时间是 “00:00” ,最晚 可能的时间…...
第三节课 Linux文件权限
目录 文件属性详解 权限修改 文件所有者与属组修改 文件默认权限修改 Linux是多人多任务的操作系统,因此可能常常会有多人使用一台机器, 为了考虑每个人的隐私、方便用户合作,每个文件都有三类用户,权限是基于这三类用户设定的…...
开发STC89C51系列单片机需要的单片机技术
端口操作:控制单片机的输入输出端口,与外界进行通信。中断优先级:当多个中断同时发生时,确定哪个中断优先级更高,优先响应。时钟模块:控制单片机的时钟,可以精确计时。PWM技术:实现模…...
分布式键值存储是什么?(分布式键值存储大值)
文章目录 什么是分布式键值存储?分布式键值存储“大值”指什么? 什么是分布式键值存储? 分布式键值存储是一种分布式数据存储系统,它将数据存储为键值对的形式,并将这些键值对分散在多个节点上。每个节点都可以独立地…...
多线程(线程同步和互斥+线程安全+条件变量)
线程互斥 线程互斥: 任何时刻,保证只有一个执行流进入临界区访问临界资源,通常对临界资源起到保护作用 相关概念 临界资源: 一次仅允许一个进程使用的共享资源临界区: 每个线程内部,访问临界资源的代码&am…...
Flutter学习——开发Flutter需要的技能
第二章 Flutter开发所需要掌握的知识 文章目录 第二章 Flutter开发所需要掌握的知识前言一、开发语言Dart语言Android/Ios知识 二、组件学习三、调试与性能优化总结 前言 上一章,介绍了Flutter的来源和平台支持及特点,这一章,来梳理一下学习…...
SPSS如何进行因子分析和主成分分析之案例实训?
文章目录 0.引言1.因子分析2.主成分分析 0.引言 因科研等多场景需要进行数据统计分析,笔者对SPSS进行了学习,本文通过《SPSS统计分析从入门到精通》及其配套素材结合网上相关资料进行学习笔记总结,本文对因子分析和主成分分析进行阐述。 1.因…...
图标字体与HTML转义字符:网页设计中的两个关键概念
在网页设计中,图标字体和HTML转义字符是两个重要的概念。图标字体用于显示网页的图标,可以让用户更加直观地理解网页的内容。而HTML转义字符则用于在网页中插入特殊的字符,以保证网页的安全性和可读性。 一、图标字体 在网页中显示图标&#…...
Markdown全能助手:OpenClaw+GLM-4.7-Flash文档处理流水线
Markdown全能助手:OpenClawGLM-4.7-Flash文档处理流水线 1. 为什么需要自动化文档流水线 去年参与一个开源项目时,我每天要花3小时处理技术文档——从收集issue反馈到整理API变更,最后生成更新日志。最痛苦的是手动调整Markdown格式&#x…...
如何通过MCP协议实现AI助手与Figma设计的双向交互
如何通过MCP协议实现AI助手与Figma设计的双向交互 【免费下载链接】cursor-talk-to-figma-mcp Cursor Talk To Figma MCP 项目地址: https://gitcode.com/GitHub_Trending/cu/cursor-talk-to-figma-mcp 在当今的设计开发工作流中,设计工具与AI助手之间的割裂…...
FastLED NeoMatrix:嵌入式LED矩阵的GFX抽象与硬件加速融合框架
1. FastLED NeoMatrix:面向嵌入式显示系统的高性能LED矩阵驱动框架FastLED NeoMatrix 是一个专为嵌入式平台设计的、与 Adafruit_GFX 兼容且深度适配 FastLED 生态的 LED 矩阵显示库。它并非简单复刻,而是对原有 Adafruit_NeoMatrix 库的一次底层重构与性…...
OpenClaw学习助手:百川2-13B驱动的自动化笔记整理系统
OpenClaw学习助手:百川2-13B驱动的自动化笔记整理系统 1. 为什么需要自动化笔记整理 作为一个经常需要阅读大量技术文档和论文的开发者,我发现自己陷入了一个困境:每次下载新的PDF或PPT文件后,要么没时间仔细阅读,要…...
EBioMedicine(IF=10.8)英国伦敦国王学院等团队:融合CT深度学习、CT放射组学与外周血免疫特征在症状患者队列中诊断肺癌的研究
01文献学习今天分享的文献是由英国伦敦国王学院综合癌症中心、英国伦敦大学学院等团队于2026年2月在《eBioMedicine》(中科院1区top,IF10.8)上发表的研究“Fusing data from CT deep learning, CT radiomics and peripheral blood immune pro…...
Step3-VL-10B-Base与卷积神经网络结合:图像理解性能提升
Step3-VL-10B-Base与卷积神经网络结合:图像理解性能提升 在图像识别任务中,传统卷积神经网络(CNN)虽然擅长提取局部特征,但在处理复杂语义理解、多模态上下文推理等任务时往往表现有限。而视觉-语言大模型(…...
NaViL-9B图文对话教程:上传图片即问即答,新手零基础快速上手
NaViL-9B图文对话教程:上传图片即问即答,新手零基础快速上手 1. 认识NaViL-9B:你的智能图文助手 NaViL-9B是一款强大的多模态大语言模型,它能同时理解文字和图片内容。想象一下,你有一个既能聊天又能"看"图…...
从零开始:在VMware虚拟机上部署FreeNAS的完整指南
1. 为什么选择在VMware上部署FreeNAS? 如果你正在寻找一个经济实惠又灵活的NAS解决方案,在VMware虚拟机上跑FreeNAS绝对是个明智的选择。我最早接触这个方案是在帮朋友搭建家庭媒体中心时,当时用实体机装FreeNAS总觉得太浪费硬件资源…...
Lightpanda无头浏览器:11倍性能提升的自动化革命指南
Lightpanda无头浏览器:11倍性能提升的自动化革命指南 【免费下载链接】browser The open-source browser made for headless usage 项目地址: https://gitcode.com/GitHub_Trending/browser32/browser 你是否厌倦了传统浏览器在自动化任务中消耗大量内存&…...
KART-RERANK在Typora中的潜力应用:Markdown笔记内容的智能链接与推荐
KART-RERANK在Typora中的潜力应用:Markdown笔记内容的智能链接与推荐 不知道你有没有过这样的经历:在Typora里奋笔疾书,写一篇关于“机器学习模型评估”的笔记时,突然想起几个月前好像写过一篇关于“交叉验证”的详细总结&#x…...
