Задача №113651. Марио
Около полугода назад было доказано, что проверка возможности прохождения уровня в классической игре Super Mario Bros. лежит в классе сложности PSPACE и, более того, является PSPACE -полной задачей. Мы не предлагаем вам понять, что это значит, но предлагаем почувствовать, насколько сложно бывает программно играть в компьютерные игры. Для этого мы опишем упрощённый вариант игры и предложим проверить, возможно ли пройти уровень в нашем варианте «Марио» или нет (для понимания задачи необязательно быть знакомым с оригинальной игрой).
Наш вариант игры происходит на клетчатом поле, состоящем из n строк на m столбцов. Каждая клетка поля может принадлежать одному из следующих видов:
- пустая клетка, обозначается символом подчёркивания ' _ ';
- клетка с землёй, обозначается решёткой ' # ';
- клетка, содержащая монетку, обозначается строчной английской буквой ' c ';
- клетка, в которой находится Марио, обозначается строчной английской буквой ' m ';
- клетка, в которой находится Принцесса, обозначается строчной английской буквой ' p '.
Пронумеруем строки сверху вниз числами от 1 до n и столбцы слева направо целыми числами от 1 до m . Где-то в m -м столбце находится Принцесса (в клетке, обозначенной буквой ' p '). А в одной из клеток первого столбца стоит Марио (в клетке, обозначенной ' m '). Конечно, и Принцесса, и Марио стоят на земле, то есть в клетках, под каждым из них находится земля.
Также в некоторых столбцах от второго до ( m - 1) -го, возможно, находятся монетки. В одном столбце находится не более одной монетки, а также любая монетка лежит на земле, то есть в клетке под монеткой обязательно находится земля.
Марио, как и в классическом варианте игры, нужно добраться до Принцессы, но еще ему необходимо собрать все монетки, которые есть на поле. Марио может перемещаться только посредством прыжков.
Прыжок Марио состоит из двух частей: сначала он летит вертикально вверх, а потом горизонтально вправо. Вертикальная часть прыжка может иметь длину y от 0 до a клеток, а горизонтальная может иметь длину x от 0 до b клеток. В частности, Марио может прыгнуть вертикально вверх, не перемещаясь по горизонтали, а также прыгнуть горизонтально вправо, не смещаясь при этом по вертикали. Естественно, Марио не может пролетать сквозь клетки, содержащие землю. Обратите внимание, в отличие от оригинальной игры Марио не может перемещаться влево.
Если после окончания прыжка Марио оказывается в клетке, под которой нет земли, он падает вниз, пока под ним не окажется земля. В случае, если Марио долетает до n -й (самой нижней) строки, он проваливается вниз за экран и погибает, а игра заканчивается. Также Марио не может выпрыгивать за границы поля сверху или справа.
Если Марио оказывается в клетке с монеткой (возможно, в процессе прыжка), то он её подбирает.
Определите, возможно ли добраться до клетки с Принцессой, подобрав все монетки.
В первой строке содержится 4 целых числа n , m , a , b ( 2 ≤ n , m ≤ 100 , 1 ≤ a , b ≤ 10 ) — размеры поля и ограничения на длину прыжка Марио.
Далее следуют n строк по m символов, описывающих уровень. Каждый символ является одним из следующих: ' _ ', ' # ', ' c , ' m ', ' p ' (см. описание клеток в основной части условия).
Гарантируется, что на поле находятся единственная клетка с Марио и единственная клетка с Принцессой.
Гарантируется, что в каждом столбце от второго до ( m - 1) -го включительно находится не более одной монетки, а в первом и последнем столбце монеток нет.
Гарантируется, что Марио, Принцесса и монетки находятся в клетках, непосредственно под которыми есть клетки с землёй, в частности, Марио, Принцесса и монетки не находятся в n -й строке.
Выведите слово « YES » (без кавычек), если Марио может собрать все монетки с поля и оказаться в клетке с Принцессой, в противном случае выведите слово « NO » (без кавычек).
В первом примере Марио должен сделать два прыжка. Первым прыжком на 1 клетку вправо Марио подберёт монетку, а вторым на одну клетку вверх и две клетки вправо доберётся до принцессы.
Во втором примере Марио не может добраться до принцессы. Обратите внимание, Марио не может находиться в последней строке, так как он проваливается вниз за экран и погибает.
В четвёртом примере Марио не может сразу прыгнуть к Принцессе, потому что он должен подобрать монетку, но если он прыгнет вправо и вниз к монетке, то он не сможет потом вернуться обратно к Принцессе (обратите внимание, Марио не может вернуться обратно в стартовую точку, потому что он не умеет прыгать влево), поэтому ответ на этот тест — « NO ».
3 4 1 2 ___p mc_# ##_#
YES
4 5 10 3 __#_p mc__# ##___ _____
NO
5 3 3 2 ___ _#_ _#p m_# ##_
YES
4 4 1 3 m__p #__# _#c_ __#_
NO