| 题目名称 | 1043. [Clover S2] Freda的迷宫 |
|---|---|
| 输入输出 | mazea.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Makazeu
于2012-08-23加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：9， 提交：18， 通过率：50% | ||||
 szzy |
100 | 0.000 s | 0.00 MiB | C++ |
 RP++ |
100 | 0.020 s | 1.61 MiB | C++ |
 vector |
100 | 0.020 s | 1.86 MiB | C++ |
 稠翼 |
100 | 0.026 s | 16.34 MiB | Pascal |
 Magic_Sheep |
100 | 0.036 s | 7.84 MiB | C++ |
 sk_code |
100 | 0.043 s | 1.27 MiB | C++ |
|
sk_code |
100 | 0.066 s | 1.01 MiB | C++ |
|
RP++ |
100 | 0.149 s | 98.14 MiB | C++ |
 Skyo |
100 | 0.738 s | 86.39 MiB | C++ |
 wangyucheng |
90 | 0.029 s | 5.37 MiB | C++ |
| 关于 Freda的迷宫 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
我dfs超时
 xzcxzc11
2017-03-15 17:04
1楼
| ||||
-
Freda 的迷宫
(mazea.pas/.c/.cpp)
题目叙述
Freda 是一个迷宫爱好者，她利用业余时间建造了许多迷宫。每个迷宫都是由若干房间
和走廊构成的，每条走廊都连接着两个不同的房间，两个房间之间最多只有一条走廊直接相
连，走廊都是双向通过。
黄昏时候，Freda 喜欢在迷宫当中漫步。每天，Resodo 都会为Freda 设计一个挑战方案。
Resodo 会指定起点和终点，请Freda 来找到一条从起点到终点的简单路径。一条简单路径定
义为一个房间序列，每个房间至多在序列里出现一次，且序列中相邻的两个房间有走廊相连。
当起点和终点之间存在且仅存在一条简单路径的时候，Freda 认为这个挑战方案是RD 的。现
在，请你帮帮Resodo 来写一个程序，判断一个挑战方案是否是RD 的。
输入格式
第一行三个整数N,M,Q.分别表示房间数，走廊数，询问数。
接下来M 行每行2 个整数x,y, 0
接下来Q 行每行2 个整数x,y, 表示询问以x 为起点,y 为终点的挑战方案是否是RD 的.
输出格式
对于每个询问，输出一行”Y”或者”N”（不含引号）.Y 表示该询问所表示的挑战方案
是RD 的,N 表示该询问所表示的挑战方案不是RD 的.
输入样例
6 5 3
1 2
2 3
2 4
2 5
4 5
1 3
1 5
2 6
输出样例
Y
N
N
样例解释
1,3 之间只有一条路径1->2->3
1,5 之间有两条路径1->2->5 ; 1->2->4->5
1,6 之间没有路径
数据范围与约定
对于30%的数据，N<=100， M<=1000, Q<=100.
对于50%的数据，N<=1000, M<=10000, Q<=1000.
对于100%的数据，N<=10000, M<=100000, Q<=10000.