CF750H.New Year and Snowy Grid

NOI/NOI+/CTSC

通过率：0%

时间限制：9.00s

内存限制：256MB

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

Pay attention to the output section below, where you will see the information about flushing the output.

Bearland is a grid with h rows and w columns. Rows are numbered 1 through h from top to bottom. Columns are numbered 1 through w from left to right. Every cell is either allowed (denoted by '.' in the input) or permanently blocked (denoted by '#').

Bearland is a cold land, where heavy snow often makes travelling harder. Every day a few allowed cells are temporarily blocked by snow. Note, that this block works only on this particular day and next day any of these cells might be allowed again (unless there is another temporarily block).

It's possible to move directly between two cells only if they share a side and none of them is permanently or temporarily blocked.

Limak is a little polar bear who lives in Bearland. His house is at the top left cell, while his school is at the bottom right cell. Every day Limak should first go from his house to the school and then return back to his house. Since he gets bored easily, he doesn't want to visit the same cell twice on one day, except for the cell with his house, where he starts and ends. If Limak can reach a school and return home avoiding revisiting cells, he calls a day interesting.

There are q days you must process, one after another. For each of these days you should check if it's interesting and print "YES" or "NO" on a separate line. In order to be able to read the description of the next day you should print the answer for the previous one and flush the output.

It's guaranteed that a day with no cells temporarily blocked by snow would be interesting. It's also guaranteed that cells with Limak's house and school are never blocked (neither permanently or temporarily).

请注意下方的输出部分，其中包含有关刷新输出的信息。

Bearland 是一个有 $h$ 行 $w$ 列的网格。行从上到下编号为 $1$ 至 $h$ ，列从左到右编号为 $1$ 至 $w$ 。每个格子要么是允许通行的（在输入中用 . 表示），要么是永久阻塞的（在输入中用 # 表示）。

Bearland 是一片寒冷的土地，大雪常常使出行变得困难。每天，若干个允许通行的格子会因积雪而被临时阻塞。注意，这种阻塞仅在当天生效；次日这些格子可能再次变为允许通行（除非当天又发生了新的临时阻塞）。

仅当两个格子共享一条边，且二者均未被永久或临时阻塞时，才允许在这两个格子之间直接移动。

Limak 是一只住在 Bearland 的小北极熊。他的家位于左上角格子，学校位于右下角格子。每天，Limak 都需先从家前往学校，再从学校返回家中。由于他很容易感到厌烦，因此他不希望在同一天内访问同一个格子两次（家所在的格子除外，因为他在该格子出发并最终返回）。

若 Limak 能够在不重复访问任何格子（家所在格子除外）的前提下，从家到达学校并再返回家中，则称这一天为“有趣的”。

你需要依次处理 $q$ 天的情况。对于每一天，你应判断其是否为“有趣的”，并在单独一行输出 "YES" 或 "NO"。为了能够读取下一天的描述，你必须在输出上一天的答案后立即刷新输出。

题目保证：没有任何格子被临时阻塞（即无积雪）的日子一定是“有趣的”。同时保证 Limak 的家和学校所在的格子永远不会被阻塞（无论是永久还是临时）。

输入格式

The first line of the input contains three integers h, w and q (2 ≤ h, w ≤ 1000, 1 ≤ q ≤ 10 000) — the height and the width of the grid, and the number of days, respectively.

Next h lines describe which cells are allowed and which permanently blocked. The i-th line contains a string of length w, describing the i-th row. Every character is either '.' (denoting an allowed cell) or '#' (denoting a permanently blocked cell). It's guaranteed that a day with no cells temporarily blocked by snow would be interesting.

Then, the description of q days is given. The description of the i-th day starts with a line containing a single integer k__i (1 ≤ k__i ≤ 10) — the number of cells that are temporarily blocked by snow on that day. Each of next k__i lines contains two integers r__i, j and c__i, j (1 ≤ r__i, j ≤ h, 1 ≤ c__i, j ≤ w), representing a cell at the intersection of the row r__i, j and the column c__i, j. The given k__i cells are distinct and none of them is permanently blocked. Also, none of them contains Limak's house or school.

输入的第一行包含三个整数 $h$ 、 $w$ 和 $q$ （ $2 \le h, w \le 1000$ ， $1 \le q \le 10\,000$ ），分别表示网格的高度、宽度以及天数。

接下来的 $h$ 行描述哪些格子是允许通行的、哪些是永久阻塞的。第 $i$ 行包含一个长度为 $w$ 的字符串，描述第 $i$ 行。每个字符要么是 .（表示允许通行的格子），要么是 #（表示永久阻塞的格子）。题目保证：在没有任何格子被积雪临时阻塞的日子里，该日子仍是有趣的。

随后给出 $q$ 天的描述。第 $i$ 天的描述以一行开始，该行包含一个整数 $k_i$ （ $1 \le k_i \le 10$ ）——表示当天被积雪临时阻塞的格子数量。接下来的 $k_i$ 行每行包含两个整数 $r_{i,j}$ 和 $c_{i,j}$ （ $1 \le r_{i,j} \le h$ ， $1 \le c_{i,j} \le w$ ），表示位于第 $r_{i,j}$ 行与第 $c_{i,j}$ 列交点处的格子。所给的 $k_i$ 个格子互不相同，且均非永久阻塞格子；此外，它们中没有一个是 Limak 的家或学校所在位置。

输出格式

For each of q days print "YES" if that day is interesting, and otherwise print "NO", both without the quotes. After printing an answer, you have to both print the end-of-line character and flush the output. Then you can proceed to the next day. You can get Idleness Limit Exceeded if you don't print anything or if you forget to flush the output.

To flush you can use (just after printing a YES/NO and end-of-line):

fflush(stdout) in C++;
System.out.flush() in Java;
stdout.flush() in Python;
flush(output) in Pascal;
See the documentation for other languages.

对于 q 天中的每一天，请输出 "YES"（若该天是有趣的），否则输出 "NO"（均不带引号）。每输出一个答案后，你必须同时输出换行符并刷新输出缓冲区，然后才能继续处理下一天。如果你未输出任何内容，或忘记刷新输出缓冲区，则会得到 Idleness Limit Exceeded（空闲超时）错误。

要刷新输出缓冲区，可在输出 "YES"/"NO" 及换行符之后使用以下方式：

C++ 中：fflush(stdout)；
Java 中：System.out.flush()；
Python 中：stdout.flush()；
Pascal 中：flush(output)；
其他语言请参阅相应文档。

输入输出样例

输入#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

说明/提示

In the first sample, there are 4 days. Drawings below show how Limak could go to school and return to his home in the second and the third day (on the left and on the right respectively). A permanently blocked cell is painted red, while cells temporarily blocked by snow are painted orange. Black and green arrows should Limak's way to the school and back to the house respectively.

For the second sample, below you can see how the grid looks like on each day, where '#' denotes a cell that is blocked, either temporarily or permanently.

在第一个样例中，共有 4 天。下方图示展示了 Limak 在第二天和第三天（分别对应左侧和右侧）如何前往学校并返回家中。永久性封锁的格子涂为红色，而被积雪临时封锁的格子涂为橙色。黑色箭头和绿色箭头分别表示 Limak 前往学校和返回家中的路径。

对于第二个样例，下方展示了每一天网格的状态，其中 # 表示被封锁的格子（无论是临时还是永久性封锁）。

输入解题思路，AI测评打分。不知道怎么写?

首页