e-olymp
Задачі

Помста Лі Чака

Помста Лі Чака

prb88 “Я хочу бути піратом!” Ми нагадуємо цю відому фразу Гайбраша Трипвуда з серії комп'ютерних ігор Monkey Island ("Остров Мавп"). Гайбраш приймав участь в іншій пригоді і серйозно потребує Вашої допомоги, тому що на цей раз це питання життя та смерті. Наш Гайбраш в останній пригоді приплив на таємничий острів (ТО), щоб знайти підказку для ще більш таємничого скарбу. Тем часом Лі Чак взнав про цю поїздку і підготував западню Гайбрашу на ТО. ТО має прямокутну форму (оскільки ми знаємо, що він таємничий) і його мапа може розглядатись як матриця такої ж розмірності. Назвемо кожен елемент матриці ділянкою. Деякі ділянки можуть бути заповнені гірськими скелями. Такі ділянки вважаються непрохідними.

Розглянемо острів, мапу якого зображено на малюнку. Ця мапа є матрицею з 6 рядків і 7 стовпців. Кімнати "R" показують ділянки зі скелями. Гайбраш повинен починати з ділянки, позначеною "g", а Лі Чак – з ділянки "l". У Гайбраша є шанс утекти з цього проклятого острова, якщо він досягне кінцевої ділянки, яку помічено символом "e" на мапі. У кожну одиницю часу Гайбраш може піти на сусідню з поточною ділянку по горизонталі або по вертикалі (але не по діагоналі), якщо в ній немає скель, або не рухатись. Тобто він може переміститися на одну ділянку вгору, вниз, праворуч, ліворуч або взагалі залишитись на місці. У наведеному прикладі Гайбраш в перший момент часу може не рухатись або піти в кімнату ліворуч від нього. Всі вказані правила застосовуються також і до руху Лі Чака, але з одним обмеженням: він не може зайти на кінцеву ділянку (помічену "e"). Тобто, кожну одиницю часу Лі Чак може піти на одну ділянку вгору, вниз, ліворуч, праворуч (якщо тільки це не "R" або "e") або стояти. Ми вважаємо, що кожну одиницю часу спочатку робить хід (або стоїть) Гайбраш, а потім ходить (або стоїть) Лі Чак, в наступну одиницю часу знову спочатку робить хід Гайбраш, а потім Лі Чак і так далі. Якщо Гайбраш і Лі Чак зустрінуться на одній ділянці, то Лі Чак миттєво вб'є нашого бідного Гайбраша.

Ваша задача полягає в тому, щоб визначити,чи є по меншій мірі один безпечний шлях чи ні. Безпечний шлях – це шлях для Гайбраша (від "g" до "e") такий, що Лі Чак не може піймати Гайбраша на цьому шляху незалежно від того, що він (Лі Чак) робить кожну одиницю часу. Наприклад, послідовність "Ліворуч, Вверх, Вверх, Вверх, Праворуч" (за 5 одиниць часу) є безпечним шляхом на наведеній мапі, тому що незалежно від того, що Лі Чак робить у ці 5 одиниць часу, він не може піймати Гайбраша.

Вхідні дані

Перший рядок входу містить єдине ціле число - кількість тестових випадків. Далі йдуть рядки даних для тестових випадків. Кожен тест починається з рядка, що містить два цілих числа R та C (4 <= R, C <= 30), які позначають кількість рядків та стовпців мапи таємничого острову відповідно. Далі йде R рядків, кожен з яких містить C символів самої мапи. Є унікальні помітки "g", "l" та "e" на мапі.
Пусті ділянки без скель позначаються символом пропуску. Всі ділянки, розміщені біля довільної межі мапи, заповнені скелями.

Вихідні дані

Для кожного тесту потрібно вивести єдиний рядок. Якщо існує, по меншій мірі, хоча б один безпечний шлях для тестового випадку, потрібно вивести слово "YES", і слово "NO", якщо такого шляху немає. Вважається, що якщо існує безпечний шлях, то для його проходження потрібно не більш ніж 1000 одиниць часу для Гайбраша.

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB
Вхідні дані
3
6 7
RRRRRRR
R_e___R
R_____R
R_RRR_R
R_gRl_R
RRRRRRR
4 5
RRRRR
R__eR
Rgl_R
RRRRR
9 13
RRRRRRRRRRRRR
R_____R___R_R
R_R_R_R_R_R_R
R___RRR_R_R_R
R_RRR___ReR_R
R_R___R_R_R_R
R_R_RRRRR_R_R
R_g________lR
RRRRRRRRRRRRR
Вихідні дані
YES
NO
YES