解题思路: 注释都敲好了。不懂自己debug跑一遍就豁然开朗。这套代码同可解决题目 2107: 误落迷宫2
注意事项:
参考代码:
import java.util.Arrays; import java.util.LinkedList; import java.util.Scanner; /** * @author fzy * @create 2021/10/12 11:58 **/ public class Main { static char [][] data; static boolean [][] isVisited;//与data一一对应 记录当前节点是否被访问 static int n,m;//n行,m列 //四个方向 右 下 左 上 static int[] dx={0,1,0,-1}; static int[] dy={1,0,-1,0}; public static void main(String[] args) { Scanner input=new Scanner(System.in); n=input.nextInt(); m=input.nextInt(); data=new char[n][m]; isVisited=new boolean[n][m]; input.nextLine(); int startX=0,startY=0;//起始位置 for (int i = 0; i < n; i++) { String str=input.nextLine(); for (int j = 0; j < m; j++) { data[i][j]=str.charAt(j); if(str.charAt(j) == '@'){ //记录起点位置 startX=i; startY=j; } } } Node huba=bfs(startX,startY, '*'); if(huba != null){ System.out.println(huba.step); }else{ System.out.println("Impossibility!"); } } static class Node{ int x;//横坐标 int y;//纵坐标 int step;//到当前节点 需要的步数 public Node(int x, int y, int step) { this.x = x; this.y = y; this.step = step; } } //广度优先搜索 第一条路径必为最短路径 //起始点 终点字符 public static Node bfs(int x,int y,char key){ LinkedList queue=new LinkedList();//双向队列 //后插 起点进队列 queue.addLast(new Node(x,y,0)); isVisited[x][y]=true;//标记该节点已经访问过 //队列为空时 表示所有路径都以遍历完 且没找到胡巴 while (!queue.isEmpty()){ //弹出队头节点表示以该节点为起始节点 继续向四个方向进行搜索 Node node = queue.removeFirst(); if(data[node.x][node.y]== key){ //表示找到目的地(胡巴) 返回该节点 return node; } //搜索该节点 四个方向的邻节点 如果可访问 则后插入队列 for (int i=0;i=0 && nextX=0 && nextY<m //边界判断 && !isVisited[nextX][nextY] //这个相邻节点没被访问过 && data[nextX][nextY] != '#' //这个相邻节点可以被访问 ){ isVisited[nextX][nextY]=true;//标记该相邻节点已经被访问 queue.addLast(new Node(nextX,nextY,node.step+1)); } } } return null; } }
0.0分
3 人评分
C语言程序设计教程(第三版)课后习题10.4 (C语言代码)浏览:586 |
C语言训练-素数问题 (C语言代码)浏览:1661 |
【蟠桃记】 (C语言代码)浏览:651 |
兰顿蚂蚁 (C++代码)浏览:1094 |
C语言程序设计教程(第三版)课后习题6.11 (C语言代码)浏览:549 |
C语言程序设计教程(第三版)课后习题7.1 (C语言代码)浏览:611 |
sizeof的大作用 (C语言代码)浏览:1452 |
出圈】指针malloc版浏览:355 |
剪刀石头布 (C++代码)浏览:1713 |
整除问题 (C语言代码)浏览:526 |