← 返回题目列表

Codeforces · 540/C

C. 冰洞

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

您玩电脑游戏。你的角色站在多层冰洞的某个层面上。为了继续前进,你需要下降一层,而唯一的方法就是从冰层中掉下来。

你所在洞穴的等级是一个n行m列的矩形方格。每个细胞要么由完整的冰要么由破裂的冰组成。从每个单元格,您可以移动到与您的单元格相邻的单元格(由于游戏引擎的某些限制,您无法在同一位置跳跃,即从单元格跳转到其自身)。如果你移动到冰块破裂的牢房,那么你的角色就会从里面掉下来;如果你移动到冰块完整的牢房,那么这个牢房上的冰就会破裂。

让我们从上到下对包含 1 到 n 的整数的行进行编号,从左到右对包含 1 到 m 的整数的列进行编号。我们将第 r 行和第 c 列交叉处的单元格表示为 (r, c)。

你待在牢房(r1,c1)中,这个牢房已经破裂,因为你刚刚从更高的层跌落到这里。你需要从单元格(r2,c2)掉下来,因为那里有通往下一层的出口。你能做到吗?

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 500) - 洞穴描述中的行数和列数。

接下来的n行每一行描述了洞穴关卡的初始状态,每行由m个字符“.”组成。 (即完整的冰)和“X”(破裂的冰)。

下一行包含两个整数,r1 和 c1 (1 ≤ r1 ≤ n, 1 ≤ c1 ≤ m) - 您的初始坐标。保证洞穴的描述在单元格(r1,c1)中包含字符“X”,即起始单元格上的冰最初破裂。

下一行包含两个整数 r2 和 c2 (1 ≤ r2 ≤ n, 1 ≤ c2 ≤ m) - 您需要掉落的单元格的坐标。最终的单元格可能与起始的单元格重合。

输出

如果可以到达目的地,则打印“YES”,否则打印“NO”。

示例

输入 #1

4 6
X...XX
...XX.
.X..X.
......
1 6
2 2

输出 #1

YES

输入 #2

5 4
.X..
...X
X.X.
....
.XX.
5 3
1 1

输出 #2

NO

输入 #3

4 7
..X.XX.
.XX..X.
X...X..
X......
2 2
1 6

输出 #3

YES

注意

在第一个示例测试中,一个可能的路径是:

$$(1,6)\右箭头(2,6)\右箭头(3,6)\右箭头(4,5)\右箭头(4,4)\右箭头(4,3)\右箭头(4,2)\右箭头(4,1)\右箭头(3,2)\右箭头(2,3)\右箭头(2,2)$$

第一次访问牢房 (2, 2) 后,其上的冰裂开,当你第二次踏入那里时,你的角色会按预期掉入冰中。