瞿肖

用户名：uq_33500452490

访问量：1676

签　名：

等　　级
排　　名	4520
经　　验	1679
参赛次数	1
文章发表	14
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

全天下的温柔共十分，你占八分，遇见你那晚的凉风秋月占一分，你说你也喜欢我的那刻占一分。

TA的其他文章

三维数组存储地图，广度搜索最短路径
浏览：95

广搜的节点存放起始地，最后递归输出节点（链表）
浏览：34

和八皇后很类似，不过八皇后的想法更简单（判断合法性繁琐），这个题多了一个有：可能这一行不放棋子
浏览：216

你可能喜欢

广搜的节点存放起始地，最后递归输出节点（链表）

　　作者: 瞿肖　　　　发表时间：2023-03-12 19:24:53 浏览：34　|　评论：0　

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

是一个广搜的模板题目，广搜可以解决两种问题：
1、求最短路径，之所以广搜是最短路径，是因为在中途一直判断，是否找到目标点，第一次找到一定是最短的。
2、围圈问题，求一个地图中，有多少个地方被围起来，只要求实现了多少次广搜，每个位子都去试一遍。记得标记走过的路哦。

import java.util.*;
	public class Main {
	static class jieDian {
		int x;
		int y;
		jieDian p;

public jieDian(int x, int y) {
			this.x = x;
			this.y = y;
		}

public jieDian(int x, int y, jieDian p) {
			this.x = x;
			this.y = y;
			this.p = p;
		}

@Override
		public String toString() {
			return "[x=" + x + ", y=" + y + "]";
		}

public jieDian() {

}

static int n = 5;
	static int m = 5;
	static int[][] chek = new int[n][m];
	static int[][] arr = new int[n][m];
	static ArrayList<String> list = new ArrayList<String>();
	//四个方向
	static int[][] mapArr = new int[][] { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };

public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				arr[i][j] = sc.nextInt();
			}
		}
		Queue<jieDian> dui = new LinkedList<Main.jieDian>();
		dui.offer(new jieDian(0, 0));
		chek[0][0] = 1;
		while (!dui.isEmpty()) {
			list.add("");
			int size = dui.size();
			for (int i = 0; i < size; i++) {
				Main.jieDian poll = dui.poll();
				int x = poll.x;
				int y = poll.y;
				if (x == n - 1 && y == m - 1) {
					outPrin(poll);
					return;
				}
				for (int j = 0; j < 4; j++) {
					int x1 = x + mapArr[j][0];
					int y1 = y + mapArr[j][1];
					if (x1 >= 0 && x1 < n && y1 >= 0 && y1 < m && arr[x1][y1] != 1 && chek[x1][y1] != 1) {
						chek[x1][y1] = 1;
						//保存是从哪一个位置来的，
						dui.offer(new jieDian(x1, y1, poll));
					}
				}
			}
		}
	}

private static void outPrin(Main.jieDian poll) {
	//递归输出路径
		if (poll == null) {
			return;
		}
		outPrin(poll.p);
		System.out.println("(" + poll.x + ", " + poll.y + ")");
	}
	}

0.0分

0 人评分

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

瞿肖

TA的其他文章

你可能喜欢

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

C二级辅导-进制转换（C语言代码）

点我有惊喜！你懂得！

C语言训练-求素数问题（C语言代码）

c primer plus 第十二章 12.1小节

广搜的节点存放起始地，最后递归输出节点（链表）

评论区

精彩推荐

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

数列有序（C语言代码）

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

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

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

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

WU-DNA （C++代码）

Manchester-字符逆序（稳，附带小问题）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）

10进制 VS 2进制

瞿肖

TA的其他文章

你可能喜欢

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

C二级辅导-进制转换 （C语言代码）

点我有惊喜！你懂得！

C语言训练-求素数问题 （C语言代码）

c primer plus 第十二章 12.1小节

广搜的节点存放起始地，最后递归输出节点（链表）

评论区

精彩推荐

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

数列有序 （C语言代码）

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

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

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

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

WU-DNA （C++代码）

Manchester-字符逆序（稳，附带小问题）

C语言训练-求1+2!+3!+...+N!的和 （C语言代码）

10进制 VS 2进制

C二级辅导-进制转换（C语言代码）

C语言训练-求素数问题（C语言代码）

　　评论区

数列有序（C语言代码）

C语言训练-求1+2!+3!+...+N!的和（C语言代码）