Городские олимпиады/1-6 курсы/Межвузовская олимпиада 2015 - командный тур


9. Порталы

Автор задачи: Соловьёв Виктор
Источник: Региональная олимпиада по программированию 2015, командный тур
Ограничение по времени: 1 с.
Ограничение по памяти: 128 МБ

Макс и Влад играют в компьютерную игру «Герои Топора и Колдовства III». Макс уже скопил огромную армию, и все что ему остается — провести своего героя по игровой карте до замка Влада, после чего — победоносно завершить партию. Вся проблема в том, что добраться до замка — не так уж и просто.

Игровая карта представляет из себя клетчатое поле из n строк и m столбцов. За один ход герой может переместиться из клетки, в которой он находится, в одну из восьми соседних, если та не содержит препятствия. За границы поля герою выходить не разрешается.

Максиму уже известно расположение всех объектов на игровой карте. В игре существует множество различных объектов, но, с точки зрения Макса, все клетки игрового поля можно поделить всего на несколько групп:

  • клетка, на которой изначально находится его герой;
  • клетка, в которой располагается замок Влада;
  • клетка с препятствием, через которую герой перемещаться не может;
  • пустая клетка;
  • клетка с двусторонним порталом;
  • клетка с входными односторонним порталом;
  • клетки с выходными односторонним порталом.

На карте может быть до восьми групп двусторонних порталов. Для обозначения каждого двустороннего портала на карте используется некоторая цифра от 1 до 8. Добравшись до одного из таких порталов, герой может переместиться в любой портал, обозначенный той же цифрой, причём Максим сам выбирает, в какой именно портал герой переместится на сей раз.

Также на карте может быть до восьми групп односторонних порталов. Каждой группе соответствует некоторая буква латинского алфавита. При этом буквы «A», «B», ..., «H» используются для обозначения входных односторонних порталов, а буквы «a», «b», ..., «h» — для обозначения выходных порталов. Добравшись до одного из входных порталов, герой перемещается в один из выходных порталов, помеченных той же (с точностью до регистра) буквой. Выбор каждого из подходящих выходных порталов, в таком случае, равновероятен. Посещение же выходного портала не позволяет совершить какого-то особенного действия.

Кроме того, герой может находиться на клетке портала, не используя его (иначе говоря — проходить через такие клетки, как через пустые).

Макс хочет найти алгоритм действий, который позволит его герою гарантированно добраться до замка Влада за конечное число ходов.

Ваша задача — написать программу, которая определит, существует ли хотя бы один такой алгоритм.

Входные данные

Первая строка входных данных содержит два целых числа, разделенных ровно одним пробелом, n и m — количество строк и количество столбцов игрового поля соответственно (2 ≤ n, m ≤ 200).

Далее следует n строк, каждая из которых содержит по m символов — описание игровой карты. Строка может содержать следующие символы:

  • «m» — если клетка является начальным расположением героя Макса;
  • «v» — если в клетке находится замок Влада;
  • «#» — если клетка занята препятствием;
  • «.» — если клетка пуста;
  • символ цифры от «1» до «8» — если в клетке находится двусторонний портал;
  • одну из букв «A», «B», ..., «H» — если в клетке находится входной односторонний портал;
  • одну из букв «a», «b», ..., «h» — если в клетке находится выходной односторонний портал.

Гарантируется, что в описании карты ровно по одному разу встречаются символы «m» и «v»; для каждого двустороннего портала существует хотя бы один другой портал, обозначенный такой же цифрой; для каждого входного портала существует хотя бы один выходной, помеченный той же (с точностью до регистра) буквой, аналогично, для каждого выходного — хотя бы один входной.

Выходные данные

В единственной строке выходных данных необходимо вывести слово «YES» (без кавычек), если для героя Макса существует способ гарантированно добраться до замка Влада за конечное число ходов, и слово «NO» (без кавычек) — в противном случае.

Примеры
Стандартный вводСтандартный вывод
2 22
m...#.3..#.d..#...v#.3
..D.#..A.#..3.#.a..#..
YES
3 11
B.a.#.b.m.A
###########
b.8..#.8..v
NO
3 7
m.A#b.v
#######
A.a.a.B
YES
Пояснения к примерам

Для второго примера входных данных правильным ответом является «NO», поскольку портал «B» ведёт не только в нижнюю часть карты, но так же и в стартовую часть карты. Таким образом, возможна ситуация, когда герой Максима вечно будет блуждать, проходя через порталы «A» и «B», оставаясь в верхней половине карты.