计科院19孙博

用户名：uq_94474674840

访问量：688

签　名：

等　　级
排　　名	13297
经　　验	931
参赛次数	0
文章发表	5
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

1209: 密码截获 java
浏览：121

你可能喜欢

bfs广度遍历 (java)

　　作者: 计科院19孙博　　　　发表时间：2021-10-02 19:26:31 浏览：257　|　评论：0　

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

bfs(广度遍历)可求最短路径,dfs(深度遍历)可求最远路径

```
import java.util.LinkedList;
import java.util.Scanner;
//通过node节点记录最短路径
public class Main {
    static char[][] map = null;

public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int row = scanner.nextInt();
        int col = scanner.nextInt();
        map = new char[row][col];
        for (int i = 0; i < map.length; i++) {
            String string = scanner.next();
            for (int j = 0; j < map[0].length; j++) {
                map[i][j] = string.charAt(j);
            }
        }
       bfs();
    }

private static void bfs() {
	  //创建队列  先进先出特点
        LinkedList<Node> nodes = new LinkedList<>();
        nodes.addLast(new Node(0, 0, 1));
		
        while (!nodes.isEmpty()) {
		//每拿出一个节点判断它上下左右能否走通  能就加入队列 
            Node node = nodes.removeFirst();
            if (node.row == map.length - 1 && node.col == map[0].length - 1) {
                System.out.println(node.step);
                break;
            }
            //0上 1下 2左 3右
            for (int i = 0; i < 4; i++) {
                switch (i) {
                    case 0:
                        if (node.row - 1 >= 0 && map[node.row - 1][node.col] == '.') {
                            Node newNode = new Node(node.row - 1, node.col, node.step + 1);
                            nodes.addLast(newNode);
                            map[node.row - 1][node.col] = '#';
                        }
                        break;
                    case 1:
                        if (node.row + 1 < map.length && map[node.row + 1][node.col] == '.') {
                            Node newNode = new Node(node.row + 1, node.col, node.step + 1);
                            nodes.addLast(newNode);
                            map[node.row + 1][node.col] = '#';
                        }
                        break;
                    case 2:
                        if (node.col + 1 < map[0].length && map[node.row][node.col + 1] == '.') {
                            Node newNode = new Node(node.row, node.col + 1, node.step + 1);
                            nodes.addLast(newNode);
                            map[node.row][node.col + 1] = '#';
                        }
                        break;
                    case 3:
                        if (node.col - 1 >= 0 && map[node.row][node.col] == '.') {
                            Node newNode = new Node(node.row, node.col - 1, node.step + 1);
                            nodes.addLast(newNode);
							//把走过的路径设置为#
                            map[node.row][node.col - 1] = '#';
                        }
                        break;

}
            }
        }
    }
}

class Node {
    int row;
    int col;
    int step;

public Node(int row, int col, int step) {
        this.row = row;
        this.col = col;
        this.step = step;
    }
}
```

0.0分

1 人评分

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

计科院19孙博

TA的其他文章

你可能喜欢

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

C语言训练-角谷猜想（C语言代码）

第一

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

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

bfs广度遍历 (java)

评论区

精彩推荐

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

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

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C++代码）（手动优化一下计算）

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

C语言训练-大、小写问题（C语言代码）

【绝对值排序】（C++代码）

回文数(一) （C语言代码）

WU-C语言程序设计教程（第三版）课后习题11.12 （C++代码）（想学链表的小伙伴可以看看）

有关字符，字符串的输入输出函数说明

永远的丰碑（C语言代码）

计科院19孙博

TA的其他文章

你可能喜欢

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

C语言训练-角谷猜想 （C语言代码）

第一

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

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

bfs广度遍历 (java)

评论区

精彩推荐

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

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

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C++代码）（手动优化一下计算）

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

C语言训练-大、小写问题 （C语言代码）

【绝对值排序】 （C++代码）

回文数(一) （C语言代码）

WU-C语言程序设计教程（第三版）课后习题11.12 （C++代码）（想学链表的小伙伴可以看看）

有关字符，字符串的输入输出函数说明

永远的丰碑 （C语言代码）

C语言训练-角谷猜想（C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

　　评论区

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C++代码）（手动优化一下计算）

C语言训练-大、小写问题（C语言代码）

【绝对值排序】（C++代码）

永远的丰碑（C语言代码）