L2-031 深入虎穴(Java)

2024-03-27数据结构与算法3 分钟154 次阅读
AI 摘要鱼粮不足,AI 今天先歇着 · 正文在下面

题目

著名的王牌间谍 007 需要执行一次任务,获取敌方的机密情报。已知情报藏在一个地下迷宫里,迷宫只有一个入口,里面有很多条通路,每条路通向一扇门。每一扇门背后或者是一个房间,或者又有很多条路,同样是每条路通向一扇门…… 他的手里有一张表格,是其他间谍帮他收集到的情报,他们记下了每扇门的编号,以及这扇门背后的每一条通路所到达的门的编号。007 发现不存在两条路通向同一扇门。

内线告诉他,情报就藏在迷宫的最深处。但是这个迷宫太大了,他需要你的帮助 —— 请编程帮他找出距离入口最远的那扇门。

输入格式:
输入首先在一行中给出正整数 N(≤105){N(\leq 10^5)},是门的数量。最后 N{N} 行,第 i{i} 行(1≤i≤N{1\leq i\leq N})按以下格式描述编号为 i 的那扇门背后能通向的门:

shell 复制代码
K D[1] D[2] ... D[K]

其中 K 是通道的数量,其后是每扇门的编号。

输出格式:
在一行中输出距离入口最远的那扇门的编号。题目保证这样的结果是唯一的。

输入样例:

shell 复制代码
13
3 2 3 4
2 5 6
1 7
1 8
1 9
0
2 11 10
1 13
0
0
1 12
0
0

输出样例:

shell 复制代码
12
shell 复制代码
代码长度限制					16 KB
时间限制						400 ms
内存限制						64 MB

题解

这是一开始用深度搜索解题,但发现有两个样例不通过,排查不出问题所在。

java 复制代码
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

// L2-031 深入虎穴
public class Main {

	static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

	static int[][] map; // 每扇门连通其他门
	static int maxNum = -1, maxDepth = 0, n;

	private static int ini() throws Exception {
		st.nextToken();
		return (int) st.nval;
	}

	public static void main(String[] args) throws Exception {
		n = ini();
		map = new int[n + 1][];

		for (int i = 1; i <= n; i++) {
			int m = ini();
			map[i] = new int[m + 1];
			for (int j = 1; j <= m; j++) {
				int r = ini();
				map[i][j] = r;
			}
		}

		for (int i = 1; i <= n; i++) {
			// 从第 i 个门进入,看看最深能走多远
			if (map[i].length == 0)
				continue;
			dfs(i, 1);
		}

		System.out.println(maxNum);
	}

	/**
	 * 深度优先搜索
	 * 
	 * @param cur   当前门的编号
	 * @param depth 深度
	 */
	private static void dfs(int cur, int depth) {
		// 当前深度比之前的深,更新距离入口最远的那扇门的编号
		if (depth > maxDepth) {
			maxDepth = depth;
			maxNum = cur;
		}
		int[] road = map[cur];
		for (int i = 1; i < road.length; i++) {
			// 依次访问当前门能走的其他路
			dfs(road[i], depth + 1);
		}
	}
}

发现深度搜索有两个测试样例不通过,没找到问题。。。
image.png

试试广度优先搜索,这里重新调整下数据结构。

java 复制代码
import java.io.*;
import java.util.*;

// L2-031 深入虎穴
public class Main {

	static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

	/**
	 * 读取下一个整数
	 * 
	 * @return
	 * @throws Exception
	 */
	private static int ini() throws Exception {
		st.nextToken();
		return (int) st.nval;
	}

	static int N = 100001, n, idx, maxNum, maxDepth;
	// 记录结点编号
	static int[] e = new int[N];
	// 邻接数组,存储指向邻接节点的下标
	static int[] ne = new int[N];
	// 头数组,存储每个编号对应的头结点下标
	// 根据下标在 e数组 中获取相应的编号
	// 在 ne数组 中获取相邻节点的下标
	static int[] h = new int[N];
	static boolean[] vis = new boolean[N]; // 标记是否有入度,找入口,无入度即为出口(题目说明只有一个入口)

	public static void main(String[] args) throws Exception {
		n = ini();
		Arrays.fill(h, -1); // 初始化头数组为-1

		// 13
		// 1: 2 - 3 - 4 ->
		// 2: 5 - 6 ->
		// 3: 7 ->
		// 4: 8 ->
		// 5: 9 ->
		// 6: >
		// 7: 11 - 10 ->
		// 8: 13 ->
		// 9: >
		// 10: >
		// 11: 12 - >
		// 12: >
		// 13: >

		// 读取节点信息并构建邻接表
		for (int i = 1; i <= n; i++) {
			int m = ini();
			for (int j = 0; j < m; j++) {
				// 读取当前邻接节点的值
				int r = ini();
				// 存在入度,有门通向它
				vis[r] = true;
				// 将当前节点与邻接节点加入邻接表中
				addNode(i, r);

			}
		}

		// 遍历未被访问的节点,执行深度优先搜索
		for (int i = 1; i <= n; i++) {
			if (!vis[i]) // 当没有门通向它的时候它是入口,从入口开始层次遍历
				bfs(i); // 调用广度优先搜索
//				dfs(i, 1); // 调用深度优先搜索
		}

		System.out.println(maxNum);
	}

	/**
	 * 邻接表添加边
	 * 
	 * @param head     头结点编号
	 * @param neighbor 邻接节点
	 */
	private static void addNode(int head, int neighbor) {
		e[idx] = neighbor; // 在数组中存储每个节点(题目中已确定没有其他节点可以到达当前邻接点)
		ne[idx] = h[head]; // 记录当前结点相邻的节点,即上一个头结点
		h[head] = idx++; // 更新当前编号的头结点下标
	}

	/**
	 * 广度优先搜索
	 * 
	 * @param root
	 */
	private static void bfs(int root) {
		Queue<Integer> qu = new LinkedList<>();
		qu.add(root);
		int t = 0;
		while (!qu.isEmpty()) {
			// 拿到编号,从编号的头结点开始访问邻接点,加入队列
			t = qu.poll();
			for (int index = h[t]; index != -1; index = ne[index]) {
				// 得到当前下标对应的编号
				int j = e[index];
				qu.add(j);
			}
		}
		maxNum = t;
	}

	/**
	 * 深度优先搜索
	 * 
	 * @param cur  当前节点编号
	 * @param deep 当前深度
	 */
	private static void dfs(int cur, int deep) {
		if (deep > maxDepth) {
			maxDepth = deep;
			maxNum = cur;
		}
		// 获取当前编号的头结点下标,陆续访问其邻接点
		for (int index = h[cur]; index != -1; index = ne[index]) {
			// 得到当前下标对应的编号
			int j = e[index];
			dfs(j, deep + 1);
		}
	}

}
image.png
觉得有用就点个赞,不用登录也能读

评论

0 条
登录 之后才能评论
—
还没有评论,来说第一句