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.
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
901232:
4 5
01234
12345
23456
345673:
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; }
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.
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:
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:
- 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.
- 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.
- 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.
- 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.