| [Home|Training|Problems|Contests|C Language] | [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 |