| Codeforces Round 301 (Div. 2) |
|---|
| Закончено |
Вы играете в компьютерную игру. Ваш персонаж находится на одном из уровней многоуровневой ледяной пещеры. Чтобы продолжить двигаться дальше, необходимо спуститься на уровень ниже, и единственный способ это сделать — провалиться под лед.
Уровень пещеры, где вы находитесь, представляет собой прямоугольную клетчатую сетку из 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».
4 6
X...XX
...XX.
.X..X.
......
1 6
2 2
YES
5 4
.X..
...X
X.X.
....
.XX.
5 3
1 1
NO
4 7
..X.XX.
.XX..X.
X...X..
X......
2 2
1 6
YES
В первом тестовом примере существует, например, такой маршрут:
После первого посещения клетки (2, 2) лед на ней треснет, а, наступив туда во второй раз, ваш персонаж провалится под нее, что и было нужно.
