计科院20级刘磊

用户名：1579364808

访问量：4389

签　名：

写代码困了，就喝杯Java咖啡提提神

等　　级
排　　名	2497
经　　验	2278
参赛次数	6
文章发表	16
年　　龄	19
在职情况	学生
学　　校	怀化学院
专　　业	计算机科学与技术

　　自我简介：

计算机科学与技术专业的一名小码农

TA的其他文章

回溯法解决全排列
浏览：323

你可能喜欢

C语言程序设计教程（第三版）课后习题5.4 （Java代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

找寻小妖--bfs(Java)

　　作者: 计科院20级刘磊　　　　发表时间：2021-10-07 19:58:20 浏览：96　|　评论：0　

原题链接：找寻小妖

这题简直和[2177](https://www.dotcpp.com/oj/problem2177.html "2177")和[2178](https://www.dotcpp.com/oj/problem2178.html "2178")是一样的模板(这两题我的题解[2177:走迷宫--图的广度优先搜索](https://blog.dotcpp.com/a/80206 "2177: 信息学奥赛一本通T1252-走迷宫--图的广度优先搜索"),[2178:迷宫问题--BFS最短路径输出](https://blog.dotcpp.com/a/80210 "T1255-迷宫问题--BFS最短路径输出")),建议都敲一遍,加深印象.
不同的是,这回不知道起点和终点,所以可以先遍历一遍图找到起点和终点.
上代码:
```java
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int m = input.nextInt();
        int n = input.nextInt();
        char[][] maze = new char[m][n];
        for (int i = 0; i < m; i++) {
            maze[i] = input.next().toCharArray();
        }
        Point start=null;
        Point end = null;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(maze[i][j]=='@'){
                    start = new Point(i,j);
                }
                if(maze[i][j]=='*'){
                    end = new Point(i,j);
                }
                if(start!=null&&end!=null)break;
            }
        }
        bfs(maze,start,end);
    }

public static void bfs(char[][] maze,Point start,Point end) {
        Queue<Point> queue = new ArrayDeque<>();
        queue.add(start);
        int []dx = {0,1,0,-1};
        int []dy = {1,0,-1,0};
        //我刚开始boolean写成大写了 一定不能错   不然就空指针了
        boolean visited[][] = new boolean[maze.length][maze[0].length];
        //开始标记为已走
        visited[start.x][start.y] = true;
        while(!queue.isEmpty()){
               Point cur = queue.poll();
               //不同对象   不能直接 cur ==end 不然要重写equals之后再用equals
               if(cur.x==end.x&&cur.y==end.y){
                   System.out.println(cur.step);
                   return;
               }
            for (int i = 0; i < 4; i++) {
                int nextX=cur.x+dx[i];
                int nextY=cur.y+dy[i];

if(nextX>=0&&nextX<maze.length&&nextY>=0&&nextY<maze[0].length){
                   if(maze[nextX][nextY]!='#'&&visited[nextX][nextY]==false){
                       Point next = new Point(nextX,nextY);
                       queue.add(next);
                       next.step= cur.step+1;
                       visited[nextX][nextY]=true;
                   }
               }
            }
        }
        System.out.println("Impossibility!");
    }
}

class Point {
    int x;
    int y;
    int step;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
        step = 0;
    }
}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

计科院20级刘磊

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.4 （Java代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

找寻小妖--bfs(Java)

评论区

精彩推荐

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

矩阵乘法（C++代码）

【回文数(二)】（C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

WU-拆分位数（C++代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

1908题解

【亲和数】（C语言代码）

计科院20级刘磊

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.4 （Java代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

找寻小妖--bfs(Java)

评论区

精彩推荐

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码）

矩阵乘法 （C++代码）

【回文数(二)】 （C语言代码）

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

WU-拆分位数 （C++代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

1908题解

【亲和数】 （C语言代码）

　　评论区

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）

矩阵乘法（C++代码）

【回文数(二)】（C语言代码）

WU-拆分位数（C++代码）

【亲和数】（C语言代码）