← 返回题目列表

Codeforces · 1583/C

C. 奥姆卡和决心

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

问题陈述出现在下面,让你充满决心。

考虑一个网格,其中一些单元格为空,一些单元格已填充。如果从该单元格开始,您可以通过仅向上和向左移动穿过空单元格来退出网格,则称该网格中的单元格可退出。这包括单元格本身,因此所有填充的单元格都不可退出。请注意,您可以通过向左从任何最左边的空单元格(第一列中的单元格)退出网格,并通过向上从任何最上面的空单元格(第一行中的单元格)退出网格。

如果只给定哪些单元格可退出,我们就可以准确地确定哪些单元格被填充,哪些未被填充,那么我们称网格为可确定的。

给你一个网格 $$$a$$$ ,尺寸为 $$$n \times m$$$ ,i。 e.具有 $$$n$$$ 行和 $$$m$$$ 列的网格。您需要回答 $$$q$$$ 查询 ($$$1 \leq q \leq 2 \cdot 10^5$$$)。每个查询给出两个整数 $$$x_1, x_2$$$ ($$$1 \leq x_1 \leq x_2 \leq m$$$) 并询问由 $$$x_1, x_1 + 1, \ldots, x_2 - 1, x_2$$$ 列组成的 $$$a$$$ 子网格是否可确定。

输入

第一行包含两个整数 $$$n, m$$$ ($$$1 \leq n, m \leq 10^6$$$, $$$nm \leq 10^6$$$) — 网格 $$$a$$$ 的尺寸。

$$$n$$$ 行如下。第 $$$y$$$ 行包含 $$$m$$$ 个字符,如果第 $$$y$$$ 行和第 $$$x$$$ 列的交集处的单元格填充为“.”,则第 $$$x$$$ 为“X”。如果它是空的。

下一行包含一个整数 $$$q$$$ ($$$1 \leq q \leq 2 \cdot 10^5$$$) — 查询数。 接下来是

$$$q$$$ 行。每行包含两个整数 $$$x_1$$$ 和 $$$x_2$$$ ($$$1 \leq x_1 \leq x_2 \leq m$$$),表示一个查询,询问包含 $$$x_1, x_1 + 1, \ldots, x_2 - 1, x_2$$$ 列的 $$$a$$$ 的子网格是否可确定。

输出

对于每个查询,如果查询指定的子网格可确定,则输出一行包含“YES”,否则输出“NO”。输出不区分大小写(因此“yEs”和“No”也将被接受)。

示例

输入 #1

4 5
..XXX
...X.
...X.
...X.
5
1 3
3 3
4 5
5 5
1 5

输出 #1

YES
YES
NO
YES
NO

注意

对于示例的每个查询,相应的子网格在下面显示两次:首先以其输入格式显示,然后将每个单元格标记为“E”(如果可退出),否则标记为“N”。

对于第一个查询:

对于第二个查询:

请注意,您可以通过从任何最左边的单元格向左(或从任何最上面的单元格向上)退出网格;您无需到达左上角单元格即可退出网格。

对于第三个查询:

这个子网格不能仅根据每个单元格是否可退出来确定,因为下面的网格也会生成上面的“可退出网格”:

对于第四个查询:

对于第五个查询:

该查询只是整个网格。不能仅根据每个单元格是否可退出来确定,因为下面的网格也会生成上面的“可退出网格”: