F. Лабиринт
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

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

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

Если посмотреть на лабиринт сверху, то его можно представить как двумерное поле из клеток, которое имеет размеры в $$$H$$$ рядов и $$$W$$$ столбцов.

Первая строка входных данных содержит два целых числа $$$H$$$ и $$$W$$$ $$$(5 \le H, W \le 100)$$$.

Следующие $$$H$$$ строк описывают лабиринт. Каждая строка содержит $$$W$$$ символов. Каждый символ описывает отдельную клетку:

  • если символ равен «.», то клетка свободна;
  • если символ равен «#», то клетка является стеной;
  • если символ равен «A», то клетка свободна и в этой клетке находится текущая позиции персонажа;
  • если символ равен «G», то клетка свободна и в этой клетке находится горшочек с золотом;
  • других символов не существует в описании лабиринта.

Гарантируется, что в описании лабиринта

  • крайние ряды и столбцы состоят только из символов «#»;
  • существует ровно один символ «A»;
  • существует ровно один символ «G».

Персонаж может переместиться из клетки $$$A$$$ в клетку $$$B$$$, если

  • клетка $$$B$$$ — свободная;
  • клетки $$$A$$$, $$$B$$$ имеют общую сторону.

Гарантируется, что если можно добраться из клетки $$$A$$$ в клетку $$$B$$$ с помощью некоторого количества перемещений, где по пути ни одна клетка не повторяется, то существует ровно одна последовательность таких перемещений.

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

Выведите «YES», если существует такая последовательность перемещений персонажа, после которых персонаж окажется в одной клетке с горшочком золота. Иначе выведите «NO».

Система оценки
ПодгруппаДополнительные ограниченияБаллыНеобходимые подгруппы
$$$1$$$ Если возможно добраться до горшочка с золотом, то нужно сделать не более $$$2$$$ перемещений$$$10$$$—
$$$2$$$ Если возможно добраться до горшочка с золотом, то нужно сделать не более $$$6$$$ перемещений$$$20$$$$$$1$$$
$$$3$$$—$$$70$$$$$$1$$$, $$$2$$$
Примеры
Входные данные
5 5
#####
#...#
#.#.#
#A#G#
#####
Выходные данные
YES
Входные данные
5 5
#####
#.G.#
#####
#A..#
#####
Выходные данные
NO
Входные данные
9 13
#############
#...........#
#.###.#######
#..G#.#.#...#
#.###.#.###.#
#.#A........#
#.#.#.#####.#
#.#.#...#...#
#############
Выходные данные
YES