La grille contient-elle un cycle ?
Étant donné une grille de hauteur
h et de largeur w remplie de lettres, vous êtes autorisé à vous déplacer uniquement sur la même lettre. Autrement dit, si vous commencez à marcher sur la lettre a, vous ne pouvez vous déplacer que sur des cellules qui contiennent la lettre a. La question est de savoir s’il est possible de se déplacer de telle sorte que vous aboutissiez sur une cellule déjà visitée auparavant. Notez qu’il n’est pas autorisé de revenir directement sur la cellule précédente. Vous pouvez uniquement vous déplacer horizontalement ou verticalement sur des cellules voisines.En d’autres termes, vous cherchez à déterminer s’il existe un cycle formé par des lettres identiques dans la grille.
Entrée
La première ligne des données d’entrée contient deux entiers
h et w (1 ≤ h, w ≤ 200).Les
h lignes suivantes contiennent chacune w caractères alphabétiques en minuscules (lettres latines).Sortie
Le programme doit afficher
Yes si la grille contient un cycle et No sinon.Exemples
Entrée | Sortie |
4 4
aaaa
abba
abbc
aaaa | Yes |
4 4
aaaa
abba
abdc
aaaa | No |
4 4
aaaa
abba
abda
aaaa | Yes |
4 4
ccca
cdcc
ccec
fccc | Yes |
3 3
abb
bcb
bba | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB