12119. Лабіринт


Відправити розв'язок

Бали: 100
Time limit: 2.0s
Memory limit: 500M

Authors:
Problem type
Allowed languages
C++, Java, Pascal, Python

У нас є сітка з \(H\) горизонтальних рядків і \(W\) вертикальних стовпців. Позначимо \((i,j)\) комірку в \(i\)-му рядку зверху та \(j\)-му стовпчику зліва. На кожній клітинці сітки написана мала англійська літера. Літера, написана на \((i,j)\), дорівнює \(j\)-му символу даного рядка \(S_i\) ​.

Snuke повторить перехід до сусідньої клітини зі спільною стороною, щоб перейти від (1,1) до \((H,W)\). Визначте, чи існує шлях, у якому літери, написані у відвіданих клітинках (включаючи початкову (1,1) і кінцеву \((H,W)\)) є \(s → n → u → k → e → s → n →…,\) у порядок відвідування. Тут клітина \((i_1 ​,j_1 ​ )\) називається суміжною клітинкою \((i_2 ​ ,j_2 ​ )\), що має спільну сторону тоді і тільки тоді, коли \(∣i_1 ​ −i_2 ​ ∣+∣j_1 ​ −j_2 ​ ∣=1\).

Формально визначте, чи існує послідовність комірок \(((i_1 ​ ,j_1 ​ ),(i_2 ​ ,j_2 ​ ),…,(i_k ​ ,j_k ​ ))\), така що:

  • \((i_1 ​ ,j_1 ​ )=(1,1),(i_k ​ ,j_k ​ )=(H,W)\);
  • \((i_{t+1} ,j_{t+1} )\) — суміжна клітинка з \((i_t ,j_t )\) зі спільною стороною для всіх \(t\) \((1≤t<k)\);
  • літера, написана на \((i_t​,j_t​)\) збігається з \((((t−1)\) mod \(5)+ 1)\)-м символом snuke для всіх \(t\) \((1≤t≤k)\).

Обмеження

  • \(2≤H,W≤500\)
  • \(H\) і \(W\) є цілими числами.
  • \(S_i\) — рядок довжиною \(W\), що складається з малих літер англійської мови.

Формат вхідних даних

Перший рядок містить цілі числа \(H,W\).

Наступні  \(H\) рядків містять \(S_i\).

Формат вихідних даних

У вихідний потік виведіть відповідь: Yes або No.

Приклад вхідних даних

2 3
sns
euk

Приклад вихідних даних

Yes

Шлях (1,1)→(1,2)→(2,2)→(2,3) задовольняє умови, оскільки на них написано s → n → u → k у порядку відвідування.

Приклад вхідних даних

2 2
ab
cd

Приклад вихідних даних

No

Приклад вхідних даних

5 7
skunsek
nukesnu
ukeseku
nsnnesn
uekukku

Приклад вихідних даних

Yes

Коментарі

Ще немає коментарів.