Prologin
2025
ÉNONCɶ
Avez-vous déjà observé comment débloquer un téléphone portable sous le système d'exploitation Android ? L'écran d'accueil affiche une surface de 3x3 cases, sur laquelle l'utilisateur doit dessiner un motif avec son doigt pour pouvoir débloquer son téléphone. Seul le motif correct débloque le téléphone.
Dans ce problème, il s'agit de calculer le nombre de motifs différents
possibles pour évaluer la sécurité de ce système. Voici comment peuvent être
formés les motifs. Le téléphone comporte un tableau de 3x3 cases. Pour former
un motif, l'utilisateur pose son doigt sur l'une de ces cases, et déplace
ensuite son doigt de cases en cases, jusqu'à ce qu'il décide de le relever de
l'écran. Au fur et à mesure que l'utilisateur déplace son doigt, les cases
visitées s'allument. Le motif final est constitué de l'ensemble des cases
allumées ainsi que l'ordre dans lequel elles ont été allumées. Passer au-dessus
d'une case déjà allumée ne change pas l'état de la case. Enfin, il est possible
de faire un déplacement du type (+2, +1) (c'est-à-dire avec une différence
d'une ligne et de deux colonnes entre deux cases successives), ainsi que toutes
les déplacements symétriques, en n'allumant que la case de départ et
d'arrivée.
Prenez l'exemple du motif suivant :
Le motif est composé de 5 cases allumées. Remarquez que l'on passe deux fois
sur la case centrale (sans changer son état la deuxième fois), et que le
déplacement entre la troisième et la quatrième case visitée est un exemple d'un
déplacement du type (+2, +1) (c'est-à-dire avec une différence de deux lignes
et d'une colonne ici), sans allumer les cases adjacentes.
Ecrivez un programme qui renvoie le nombre de motifs possibles commençant par
une case de départ donnée en entrée (le coin en haut à gauche ayant les
coordonnées (0,0)), et ayant un nombre de cases fixé.
ENTRÉE¶
- Sur la première ligne : l'entier x (entre 0 et 2, bornes incluses), la colonne de départ.
- Sur la deuxième ligne : l'entier y (entre 0 et 2, bornes incluses), la ligne de départ.
- Sur la trosième ligne : l'entier k (entre 1 et 9, bornes incluses), le nombre de cases des motifs à énumérer.
SORTIE¶
Un entier, le nombre de motifs possibles remplissant les conditions demandées.