← 返回题目列表

Codeforces · 232/E

E. 快速乌龟

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

John Doe 有一个字段,它是一个大小为 n × m 的矩形表。我们假设字段行从上到下编号为 1 到 n,字段列从左到右编号为 1 到 m。那么第 x 行和第 y 列交叉处的字段单元格的坐标为 (x; y)。

我们知道约翰视野中的一些单元格被漆成白色,一些单元格被漆成黑色。此外,约翰还有一只乌龟,它可以沿着视野中的白细胞移动。乌龟可以从坐标为 (x; y) 的白色单元格进入 (x + 1; y) 或 (x; y + 1) 单元格,如果相应的单元格被涂成白色。换句话说,海龟只能沿着区域的白细胞向右或向下移动。乌龟不能走出场地范围。

另外,John 有 q 个查询,每个查询都由四个数字 x1, y1, x2, y2 表征(x1 ≤ x2, y1 ≤ y2)。对于每个查询,约翰想知道乌龟是否可以从坐标为 (x1; y1) 的点出发,并到达坐标为 (x2; y2) 的点,仅沿着田野的白色方块移动。

输入

第一行包含两个空格分隔的整数 n 和 m (1 ≤ n, m ≤ 500) — 字段大小。

接下来的 n 行中的每一行都包含 m 个字符“#”和“.”:如果单元格 (i; j) 被涂成黑色,则第 i 行的第 j 个字符等于“#”;如果单元格 (i; j) 被涂成白色,则第 i 行的第 j 个字符等于“.”。

下一行包含整数 q (1 ≤ q ≤ 6·105) — 查询数。接下来的 q 行包含四个空格分隔的整数 x1、y1、x2 和 y2 (1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ m) — 起始和结束单元格的坐标。保证单元格 (x1; y1) 和 (x2; y2) 为白色。

输出

对于每个 q 查询,如果存在满足要求的从单元格 (x1; y1) 到单元格 (x2; y2) 的路径,则在单行上打印“是”,否则打印“否”。按顺序打印查询的答案,其中查询在输入中给出。

示例

输入 #1

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

输出 #1

No
Yes
Yes
Yes
Yes

输入 #2

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

输出 #2

Yes
Yes
Yes
No
Yes