计科院20级刘磊

用户名：1579364808

访问量：4389

签　名：

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

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

　　自我简介：

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

TA的其他文章

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

你可能喜欢

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

T1255-迷宫问题--BFS最短路径输出

　　作者: 计科院20级刘磊　　　　发表时间：2021-10-02 20:45:50 浏览：307　|　评论：0　

原题链接：信息学奥赛一本通T1255-迷宫问题

解题思路:
这个题目和[2178题  走迷宫](https://www.dotcpp.com/oj/problem2177.html "2178题")类似,可以参考我的上个题解[(2177: 信息学奥赛一本通T1252-走迷宫--图的广度优先搜索)](https://blog.dotcpp.com/a/80206 "(2177: 信息学奥赛一本通T1252-走迷宫--图的广度优先搜索)")  不同的是这里需要输出的是最短路径   我们可以用一个pre指针指向上一个点,最后用递归把最短路径的链表反向进行输出即可

```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);
        char[][] map = new char[5][5];
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                map[i][j]=input.next().charAt(0);
            }
        }
        bfs(map);
    }

public static void bfs(char[][] map) {
        Queue<Coordinate> queue = new ArrayDeque<>();
        boolean[][] visited = new boolean[map.length][map[0].length];
        int direction[][] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        queue.add(new Coordinate(0, 0));
        visited[0][0] = true;//图和树最大的不同就是图可能有环   所以需要一个visited数组来标记结点是否被访问过

while (!queue.isEmpty()) {
            Coordinate cur = queue.poll();
            if (cur.x == map.length-1 && cur.y == map[0].length-1) {
                outputPath(cur);
                break;
            }
            for (int i = 0; i < 4; i++) {
                int nextX = cur.x + direction[i][0];
                int nextY = cur.y + direction[i][1];
                if (nextX >= 0 && nextX < map.length &&  nextY >= 0 &&nextY < map[0].length) {
                    if (visited[nextX][nextY] == false && map[nextX][nextY] != '1') {
                        Coordinate temp = new Coordinate(nextX, nextY);
                        temp.pre = cur;
                        queue.add(temp);
                        visited[nextX][nextY] = true;

}
                }
            }
        }

}
    //利用递归实现倒序输出路径链表
    public static void  outputPath(Coordinate end){
        if(end==null)return;
        //递归的核心在于假设子问题已经解决       这里是假设从终点  也就是链表的首部的后面结点全部打印完了  最后打印终点  即链表首部
        outputPath(end.pre);
        System.out.println("("+end.x+", "+end.y+")");
    }

}

class Coordinate {
    int x = 0;
    int y = 0;
    Coordinate pre = null;
    public Coordinate(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
```

0.0分

2 人评分

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

计科院20级刘磊

TA的其他文章

你可能喜欢

简单的a+b （C语言代码）

C二级辅导-求偶数和（C++代码）

假币问题（C语言代码）

点我有惊喜！你懂得！

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

T1255-迷宫问题--BFS最短路径输出

评论区

精彩推荐

C二级辅导-阶乘数列（C语言代码）

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

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

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

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

A+B for Input-Output Practice (III) （C语言代码）

演讲大赛评分（C语言代码）

陈教主的三角形（C语言代码）

一元一次方程（C语言代码）

数组输出（C语言代码）

计科院20级刘磊

TA的其他文章

你可能喜欢

简单的a+b （C语言代码）

C二级辅导-求偶数和 （C++代码）

假币问题 （C语言代码）

点我有惊喜！你懂得！

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

T1255-迷宫问题--BFS最短路径输出

评论区

精彩推荐

C二级辅导-阶乘数列 （C语言代码）

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

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

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

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

A+B for Input-Output Practice (III) （C语言代码）

演讲大赛评分 （C语言代码）

陈教主的三角形 （C语言代码）

一元一次方程 （C语言代码）

数组输出 （C语言代码）

C二级辅导-求偶数和（C++代码）

假币问题（C语言代码）

　　评论区

C二级辅导-阶乘数列（C语言代码）

演讲大赛评分（C语言代码）

陈教主的三角形（C语言代码）

一元一次方程（C语言代码）

数组输出（C语言代码）