Nombre minimum de clics pour résoudre le casse-tête de type Flood-It

J’ai la grid N × M dans laquelle chaque cellule est colorée d’une couleur.

Lorsque le joueur clique sur n’importe quelle cellule de la grid de couleur α, la cellule située dans le coin supérieur gauche de la grid, de couleur β, reçoit la couleur α, mais pas seulement celle-ci: les chemins qui utilisent uniquement les couleurs α ou β reçoivent également la couleur α.

La connexion entre les cellules doit être considérée uniquement dans les directions horizontale et verticale pour former les chemins. Par exemple, lorsque le joueur clique sur la cellule mise en surbrillance dans la figure de gauche, la grid reçoit la coloration de la figure de droite. Le but du jeu est de rendre la grid monochromatique.

Cliquez sur Résultat

Description de l’entrée

La première ligne de l’entrée est constituée de 2 entiers N et M (1 ≤ N ≤ 4, 1 ≤ M ≤ 5), qui représentent respectivement le nombre de lignes et le nombre de colonnes de la grid. Les N lignes suivantes décrivent la configuration initiale de la grid, représentant chaque couleur par un entier compris entre 0 et 9. L’entrée ne consiste en aucune autre ligne.

Description de la sortie

Imprimer une ligne contenant un seul entier qui représente le nombre minimum de clics que le joueur doit faire pour rendre la grid monochromatique.

Échantillon d’entrée

1:

4 5
01234
34567
67890
90123

2:

4 5
01234
12345
23456
34567

3:

4 5
00162
30295
45033
01837

Échantillon de sortie

1:

12

2:

7

3:

dix

J’essaie de trouver une solution avec le retour arrière (à cause du délai de 8 secondes et de la petite taille de la grid). Mais il faut dépasser la limite de temps. Certaines personnes viennent de le faire sur 0 secondes.

Il existe un autre algorithme pour résoudre ce problème?

#include  #include  #define MAX 5 #define INF 999999999 typedef int signed_integer; signed_integer n,m,mink; bool vst[MAX][MAX]; signed_integer flood_path[4][2] = { {-1,0}, {1,0}, {0,1}, {0,-1} }; //flood and paint all possible cells... the root is (i,j) signed_integer flood_and_paint(signed_integer cur_grid[MAX][MAX],signed_integer i, signed_integer j, signed_integer beta, signed_integer alpha, signed_integer colors[]){ //invalid cell if (vst[i][j] || i = n || j = m) return 0; //mark existent colors colors[cur_grid[i][j]] = 1; //only alpha and beta colors counts if (cur_grid[i][j] != beta && cur_grid[i][j] != alpha) return 0; //mark (i,j) as visited and change its color vst[i][j] = true; cur_grid[i][j] = alpha; //floodit ! signed_integer ret = 1; for (signed_integer k = 0; k = mink) return; signed_integer colors[10]; memset(vst, false, sizeof(vst)); memset(colors, 0, sizeof(colors)); signed_integer beta = cur_grid[0][0]; signed_integer cont = flood_and_paint(cur_grid, 0, 0, beta, alpha, colors); //there are alpha colors to change and no beta colors to change colors[alpha] = 1; colors[beta] = 0; //all squares on same color if (cont == n * m) { mink = k; return; } //this solution is equals to another ? ... getting back if (cont == _cont) return; ++k;//new click //copy this masortingx and backtrack signed_integer copy[MAX][MAX]; for (signed_integer c = 0; c < 10; ++c){ if (colors[c] && c != cur_grid[0][0]) { memcpy(copy, cur_grid,n*m*sizeof(signed_integer)); backtrack(copy,k,cont,c); } } } void cleanBuffer(){ while (getchar() != '\n'); } int main(void) { signed_integer grid[MAX][MAX]; scanf("%d %d",&n,&m); for (signed_integer i = 0; i < n; ++i) { cleanBuffer(); for (signed_integer j = 0; j < m; ++j){ grid[i][j] = getchar() - '0'; } } mink = INF; backtrack(grid,0, 0, grid[0][0]); printf("%d\n",mink); return 0; } 

Amélioration de haut niveau

Notez que les cellules sont soit leur couleur d’origine, soit la dernière couleur sélectionnée.

Cela signifie que nous pouvons représenter l’état actuel du tableau au moyen de 20 bits (marquage de chacune des 4 * 5 cellules, qu’elles contiennent ou non la couleur d’origine) et d’un nombre compris entre 0 et 9, indiquant la dernière couleur choisie.

Il en résulte un maximum de 10 millions d’États à explorer. La fonction de retour en arrière peut éviter d’avoir à recurse si elle atteint un état déjà visité. Je m’attends à ce que ce changement accélère considérablement votre solution.

Amélioration de bas niveau

La représentation de l’état par un masque de 20 bits et la dernière couleur facilite également la mise à jour et la restauration de l’état, car seuls 2 chiffres doivent être modifiés au lieu de la mémoire de l’ensemble du tableau.

Si vous considérez le tableau 4×5 comme “19 cases sur lesquelles vous pouvez cliquer”, cela suggère qu’il y en a 19! ou 121 645 100 408 832 000 combinaisons à vérifier. Cependant, un certain nombre d’optimisations peuvent réduire considérablement le nombre de combinaisons à seulement quelques dizaines:

observations sur la stratégie de jeu

  • Cliquer sur différentes cases de même couleur a le même effet. Donc, le tableau doit être vu comme “9 couleurs (ou moins), vous pouvez cliquer sur”.
  • Les carrés adjacents de même couleur doivent être vus comme des groupes; ils agissent toujours ensemble. Dans l’exemple ci-dessous, les trois carrés blancs en bas à droite forment un tel groupe.
  • Cela n’a de sens que de cliquer sur une couleur adjacente au groupe de coins. Dans la première étape de l’exemple ci-dessous, il suffit de cliquer sur un carré rose, vert, orange ou blanc.
  • Lorsque plusieurs groupes de couleur unique (où un seul groupe a une certaine couleur) sont adjacents au groupe de coins, l’ordre dans lequel ils sont cliqués n’a pas d’importance. Dans l’exemple ci-dessous, après avoir cliqué sur 5 et 3, tout ordre de cliquer sur 4, 7, 8 et 9 aura le même résultat.
  • Lorsque tous les groupes d’une certaine couleur sont adjacents au groupe de coins, ils peuvent être vus comme des groupes de couleurs uniques. exactement un clic par couleur est nécessaire pour les connecter. Dans l’exemple ci-dessous, après avoir cliqué sur 5 et 3, les deux carrés roses et les deux carrés verts deviennent deux groupes de couleur unique.
  • Lorsque le tableau ne comporte que des groupes de couleur unique, le nombre de clics nécessaires est égal au nombre de groupes non connectés. Dans l’exemple ci-dessous, après avoir cliqué sur 5 et 3, exactement huit autres clics sont nécessaires.
  • S’il existe exactement un groupe non connecté qui a la même couleur que le groupe de coins et qu’il est séparé par plus d’un autre groupe, le groupe peut être considéré comme un groupe de couleur unique.
  • Réduire le nombre de clics signifie connecter plusieurs groupes à la fois. Cela peut être fait lorsque plusieurs groupes de même couleur sont adjacents au groupe de coins (comme lorsque vous cliquez sur 1 ou 2 à l’étape 3 de l’exemple ci-dessous), ou en cliquant sur un groupe qui sépare le groupe de coins d’un groupe de même couleur ( comme cela est le cas aux étapes 1 et 2 de l’exemple).

jeu monochrome - exemple 3 début

Algorithme basé sur une stratégie optimale

Un algorithme récursif basé sur une stratégie optimale utilisant les règles énumérées ci-dessus, suit ces étapes pour chaque récursion:

  1. S’il ne rest que des groupes de couleur unique, le nombre de clics est égal au nombre de groupes non connectés. renvoyer ce numéro.
  2. Si un groupe de la même couleur que le groupe de coins en est séparé par un seul autre groupe, cliquez sur cet autre groupe et reniflez. Si plusieurs options existent, essayez-les toutes.
  3. Si un ou plusieurs groupes de couleurs uniques (ou tous les groupes de certaines couleurs) sont adjacents au groupe de coins, cliquez dessus dans n’importe quel ordre. Puis réévaluez le tableau à partir de l’étape 1.
  4. Essayez de cliquer sur toutes les couleurs adjacentes au groupe de coins et recurse.

Une implémentation Javascript d’un algorithme de force brute nécessitait des dizaines de millions de récursions, par exemple 1 et 3 dans la question, avec un temps d’exécution bien supérieur à la limite des 8 secondes. Après avoir mis en œuvre les optimisations décrites ci-dessus, l’exemple 1 a été résolu en seulement 38 récurrences et un temps d’exécution de quelques millisecondes. Les exemples 2 et 3 étaient encore plus rapides.