问题陈述出现在下面,让你充满决心。
考虑一个网格,其中一些单元格为空,一些单元格已填充。如果从该单元格开始,您可以通过仅向上和向左移动穿过空单元格来退出网格,则称该网格中的单元格可退出。这包括单元格本身,因此所有填充的单元格都不可退出。请注意,您可以通过向左从任何最左边的空单元格(第一列中的单元格)退出网格,并通过向上从任何最上面的空单元格(第一行中的单元格)退出网格。
如果只给定哪些单元格可退出,我们就可以准确地确定哪些单元格被填充,哪些未被填充,那么我们称网格为可确定的。
给你一个网格 $$$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”。
对于第一个查询:
对于第二个查询:
请注意,您可以通过从任何最左边的单元格向左(或从任何最上面的单元格向上)退出网格;您无需到达左上角单元格即可退出网格。
对于第三个查询:
这个子网格不能仅根据每个单元格是否可退出来确定,因为下面的网格也会生成上面的“可退出网格”:
对于第四个查询:
对于第五个查询:
该查询只是整个网格。不能仅根据每个单元格是否可退出来确定,因为下面的网格也会生成上面的“可退出网格”: