← 返回题目列表

Codeforces · 750/H

H. 新年和雪格

中文机器翻译题面 查看原题

请注意下面的输出部分,您将在其中看到有关刷新输出的信息。

Bearland 是一个具有 h 行和 w 列的网格。行从上到下编号为 1 到 h。列从左到右编号为 1 到 w。每个单元格要么被允许(在输入中用“.”表示),要么被永久阻止(用“#”表示)。

熊地是一片寒冷的土地,那里的大雪常常使旅行变得更加困难。每天,一些允许的牢房都会被雪暂时封锁。请注意,此阻止仅在这一特定日期有效,第二天任何这些单元格都可能再次被允许(除非有另一个临时阻止)。

只有当两个单元格共享一侧并且没有一个单元格被永久或暂时阻挡时,才可以在两个单元格之间直接移动。

Limak 是一只住在 Bearland 的小北极熊。他的房子位于左上角的单元格,而他的学校位于右下角的单元格。利马克每天都要先从家到学校,然后再回到家。因为他很容易感到无聊,所以他不想在一天内两次访问同一个牢房,除了他家所在的牢房,他在那里开始和结束。如果利马克能够到达学校并回家而无需再次访问牢房,他称这一天很有趣。

您必须连续处理 q 天。对于这些日子中的每一天,您都应该检查它是否有趣,并在单独的行上打印“是”或“否”。为了能够阅读第二天的描述,您应该打印前一天的答案并刷新输出。

保证没有细胞被雪暂时遮挡的一天会很有趣。它还保证利马克的房屋和学校所在的牢房永远不会被封锁(无论是永久还是暂时)。

输入

输入的第一行包含三个整数 h、w 和 q (2 ≤ h, w ≤ 1000, 1 ≤ q ≤ 10 000)——分别是网格的高度和宽度以及天数。

接下来的 h 行描述了哪些单元格被允许以及哪些单元格被永久阻止。第 i 行包含长度为 w 的字符串,描述第 i 行。每个字符都是“.” (表示允许的单元格)或“#”(表示永久阻止的单元格)。毫无疑问,没有细胞被雪暂时遮挡的一天会很有趣。

然后,给出q天的描述。第 i 天的描述以包含单个整数 ki (1 ≤ ki ≤ 10) 的行开始——当天被雪暂时阻挡的单元格数量。接下来的 ki 行包含两个整数 ri, j 和 ci, j (1 ≤ ri, j ≤ h, 1 ≤ ci, j ≤ w),表示行 ri, j 和列 ci, j 相交处的单元格。给定的 ki 细胞是不同的,并且没有一个细胞被永久阻塞。此外,其中没有一个包含利马克的房子或学校。

输出

对于 q 天的每一天,如果这一天有趣,则打印“YES”,否则打印“NO”,两者都不带引号。打印答案后,您必须打印行尾字符并刷新输出。然后你可以继续第二天。如果您不打印任何内容或忘记刷新输出,则可能会出现空闲限制超出。

要刷新,您可以使用(在打印 YES/NO 和行尾之后):

- C++ 中的 fflush(stdout);
- Java 中的 System.out.flush();
- Python 中的 stdout.flush() ;
- 帕斯卡刷新(输出);
- 请参阅其他语言的文档。

示例

输入 #1

3 5 4
.....
.....
.#...
1
1 4
1
1 5
2
2 4
3 1
2
1 5
3 3

输出 #1

NO
YES
YES
NO

输入 #2

9 31 5
...............................
...............................
.###.###.#.###...###.###.#.###.
...#.#.#.#.#.......#.#.#.#...#.
.###.#.#.#.###...###.#.#.#...#.
.#...#.#.#.#.#...#...#.#.#...#.
.###.###.#.###...###.###.#...#.
...............................
...............................
5
6 5
2 11
1 14
8 15
2 14
5
2 14
1 14
8 16
6 5
2 11
3
2 2
1 4
8 30
10
3 1
3 11
5 16
7 21
4 16
3 5
7 31
3 9
7 25
3 27
10
3 1
3 9
7 25
3 27
7 21
4 17
3 5
7 31
4 16
3 11

输出 #2

NO
YES
YES
YES
NO

注意

在第一个样本中,有 4 天。下图显示了利马克如何在第二天和第三天去学校和回家(分别为左侧和右侧)。永久阻塞的单元被涂成红色,而被雪暂时阻塞的单元被涂成橙色。黑色和绿色箭头分别是利马克去学校和回家的路。

对于第二个示例,您可以在下面看到网格每天的样子,其中“#”表示暂时或永久被阻止的单元格。