Pions – Épreuve régionale 2023

Niveau 5

Enoncé

Les amis se rendent compte que la machine du mathématicien était en fait un encodeur, le même qu’ils ont utilisé lors de la création de la machine ! Ils peuvent donc s’en servir pour aller à l’année qu’ils souhaitent... Cependant, ils confondent l’entrée et la sortie, et se retrouvent à aller dans le mauvais sens. Ne sachant plus du tout en quelle année ils ont atterri, les jeunes sortent de la machine pour tenter de se repérer avant de faire, ils l’espèrent, un bond final vers leur époque d’origine.

Les jeunes arrivent coincé dans une grotte. Le gardien est un homme de Néandertal qui joue à un jeu de société primitif — qui a dit qu'à cette époque les hommes ne s’amusaient pas ? Il leur fait comprendre de quelques grognements que s’ils le battent à son jeu, il les laissera sortir de la grotte et leur offrira quelques reliques qu’il a récolté (sinon coup d’massue !) Il faut aider les amis à gagner afin de sortir de la grotte.

Peu rassuré, le groupe inspecte le plateau de jeu. Il contient une grille de $M \times M$ cases d'entiers compris entre 1 et 10, de $3$ pions et d'une peinture approximative où est indiquée une liste $valeurs$ de $N$ entiers. C'est décidément un Néandertal en avance sur son temps.

De quelques grognements habilement nuancés, le matraqueur leur décrit les règles pour le déroulement d'une partie de $N$ tours :

  • Les pions sont tous placés au départ sur la case en haut à gauche du plateau.
  • Pour valider le tour $i$, il faut qu'un pion soit déplacé sur une case ayant pour valeur $valeurs_i$. Ce pion n'est pas forcément le i-ème pion et n'est pas obligatoirement sur la case de départ au début du mouvement (le pion bougé pourra être déplacé une nouvelle fois lors d'un autre tour).
  • Il est possible de déplacer un seul pion par tour, d'une case $X$ à $Y$ avec un coût correspondant au produit des cases d'un chemin de $X$ à $Y$ (sans diagonale). La première case $X$ n'est pas comprise dans le déplacement, donc dans le calcul du coût.
  • Si un pion est déjà sur une case de valeur $valeurs_i$, alors il n'est pas obligatoire de faire un déplacement, le coût est alors $0$.

Le score de chaque joueur est la somme de ses coûts de déplacements. Dans ce jeu, le but est d'avoir le plus petit score possible.

Malheureusement pour eux, le Néandertal se débrouille très bien à ce jeu et joue toujours de manière optimale. La seule façon pour s'en sortir est alors de jouer également de manière optimale, pour égaliser le score du gardien antédiluvien.

Il est alors nécessaire d'aider Oscar en affichant le plus petit score possible ou $-1$ si la partie est impossible.

Entrée

L'entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre de tours.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : valeurs, la liste des valeurs à visiter.
  • Sur la ligne suivante, un entier : M, la taille de chaque côté du plateau.
  • Sur les M lignes suivantes, une liste de M entiers séparés par des espaces : plateau, le plateau de jeu.

Sortie

Afficher le plus petit score possible ou $-1$, si la partie est impossible.

Contraintes

  • $1 \le N \le 12$
  • $1 \le valeurs_{i,j} \le 10$
  • $1 \le M \le 4$
  • $1 \le plateau_{i,j} \le 10$

Contraintes de performance

  • $1 \le N \le 1\,000$

Contraintes d'exécution

Utilisation mémoire maximum
100000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
3
2 5 3
4
3 1 4 1
1 2 4 5
8 8 8 8
8 9 8 2
Exemple de sortie
22
Commentaire

Une position est notée sous forme (ligne, colonne).

Déplacement

Exemple

Voici un exemple de déplacement possible de la case (1, 1), de valeur 3, à la case (2, 4), de valeur 5 (en bleu sur l'image) :

Il est possible d'avoir un coût de déplacement de $1 \times 2 \times 1 \times 4 \times 1 \times 5 = 40$ (en rouge) ou bien de $1 \times 4 \times 1 \times 5 = 20$ (en violet). D'autres chemins sont aussi possibles mais ne sont pas explicités ici.

A noter que la première case (3) n'est pas incluse dans le produit.

Jeu complet

Voici les étapes en jouant de manière optimale :

  1. Les 3 pions sont sur la case (1, 1), de valeur 3.
  2. Pour atteindre une case de valeur 2, bouger le pion 1 sur la case (2, 2) pour un coût de $1 \times 2 = 2$.
  3. Pour atteindre une case de valeur 5, bouger le pion 2 sur la case (2, 4) pour un coût de $1 \times 4 \times 1 \times 5 = 20$.
  4. Le pion 3 est déjà sur une case de valeur 3, pas de coût supplémentaire.

Le coût total est de $2 + 20 = 22$.

Exemple d'entrée
3
2 5 6
4
3 1 4 1
1 2 4 5
8 8 8 8
8 9 8 2
Exemple de sortie
-1
Commentaire

La partie est injouable car le nombre 6 n'est pas présent sur le plateau.

Exemple d'entrée
5
2 5 3 8 9
4
3 1 4 1
1 2 4 5
8 8 8 8
8 9 8 2
Exemple de sortie
39
Commentaire

Cet exemple ne sera jugé que dans les tests de performances.

Une position est notée sous forme (ligne, colone). Voici les étapes :

  1. Les 3 pions sont sur la case (1, 1) de valeur 3.
  2. Pour atteindre la case de valeur 2, bouger le pion 1 sur la case (2, 2) pour un coût de $1 \times 2 = 2$.
  3. Pour atteindre la case de valeur 5, bouger le pion 2 sur la case (2, 4) pour un coût de $1 \times 4 \times 1 \times 5 = 20$.
  4. Le pion 3 est déjà sur une case de valeur 3, pas de coût supplémentaire.
  5. Pour atteindre la case de valeur 8, bouger le pion 1 depuis la case (2, 2) jusqu'à la case (3, 2) pour un coût de $8$.
  6. Pour atteindre la case de valeur 9, bouger le pion 1 depuis la case (3, 2) jusqu'à la case (4, 2) pour un coût de $9$.

Le coût total est de $2 + 20 + 8 + 9 = 39$.