L2-031 深入虎穴(Java)
AI 摘要鱼粮不足,AI 今天先歇着 · 正文在下面
题目
著名的王牌间谍 007 需要执行一次任务,获取敌方的机密情报。已知情报藏在一个地下迷宫里,迷宫只有一个入口,里面有很多条通路,每条路通向一扇门。每一扇门背后或者是一个房间,或者又有很多条路,同样是每条路通向一扇门…… 他的手里有一张表格,是其他间谍帮他收集到的情报,他们记下了每扇门的编号,以及这扇门背后的每一条通路所到达的门的编号。007 发现不存在两条路通向同一扇门。
内线告诉他,情报就藏在迷宫的最深处。但是这个迷宫太大了,他需要你的帮助 —— 请编程帮他找出距离入口最远的那扇门。
输入格式:
输入首先在一行中给出正整数 ,是门的数量。最后 行,第 行()按以下格式描述编号为 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);
}
}
}
发现深度搜索有两个测试样例不通过,没找到问题。。。

试试广度优先搜索,这里重新调整下数据结构。
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);
}
}
}

评论
0 条—
还没有评论,来说第一句