12119. Лабіринт
У нас є сітка з \(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
Коментарі