[Login|Register]
Problems

Status

Rank

Problem 1167
Maze
Time Limit: 1000ms
Memory Limit: 65536kb
Description
有一个m×n的矩形方格迷宫,格子的编号是一个二元组(x,y),其中1<=x<=m, 1<=y<=n。每个1×1的格子四周都有墙。
现在给出p个三元组(x,y,d),表示格子(x,y)边上的一座墙被打通了。d=1、2、3、4分别表示格子上、下、左、右方向的墙被打通了。
然后,给出q个二元组(x,y),每个二元组表示一个询问,询问以这个点为起点,能否走出迷宫。
样理图:
   _ _ _
|_   _  |
|_| |_|_|
|  _|_|_|
|_|_|_ _|
Input
第一行:一个整数T,表示有T组数据。
后面接T组数据
对于每组数据,第一行:四个整数,m、n、p、q,意义见上,其中:
T<=6, m<=100, n<=100, p<=10000, q<=2500
接下来p行,每行三个整数x、y、d,表示一座墙是被打通了的(p行内容可能会有重复哦)。
接下来q行,每行两个整数x、y,表示一个询问。
Output
对于每组数据,首先输出一行Case %d:,其中%d是当前的组数。(参考:printf("Case %d:\n", cases) )
接下来有q行,每行是"YES"或"NO"。如果从这个点可以走出迷宫,则输出"YES",否则输出"NO"。
Sample Input
1
4 4 10 16
1 1 1
1 1 4
1 3 3
1 3 4
2 4 1
2 2 1
2 2 2
3 1 2
3 1 3
4 4 3
1 1
1 2
1 3
1 4
2 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4
Sample Output
Case 1:
YES
YES
YES
YES
NO
YES
NO
YES
YES
YES
NO
NO
YES
NO
NO
NO
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 1.5ms with 1 query(s).