题意：中文题目（略）
分析：其实就是一个暴力的bfs， 关键是模拟移动，判连通，以及状态的表示。
每个格子移动过程中，内部四个小三角的相对顺序是不变的，也就是移动过程中，格子是作为一个整体在移动的，，小三角只是在判连通时才用到，所以状态的表示可以将每个格子作为一个整体，这样的话，总共就是9个格子，用0~8表示，这样是否很熟悉了？ 可以用类似八数码的哈希方法，用康托展开将每一个状态hash到一个整数上，剩下的就是模拟了。
很惭愧，单是敲这个代码就用了快俩个小时……
hdu4531
#include<iostream> #include<algorithm> #include<stdio.h> #include<string.h> #include<stdlib.h> #include<queue> #include<vector> using namespace std; const int N = 3; const int M = 362880 + 10; struct Grid { int a[4]; }p[10];//保存初始时的9 个格子 char str[10]; int g[N][N];//记录移动过程中的地图，只记录对应格子的下标 0 ~ 8 bool row[N], col[N];//记录该行或该列能否移动 int a[N * N];//保存g对应的序列 int cantor[9] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320}; bool vis[M]; int dir[4][3][3] = { {{-1,0,1}, {0,0,2}, {0,0,3}}, {{0,0,1}, {0,0,2}, {1,0,-1}}, {{0,0,-1}, {0,0,-2}, {0,-1,1}}, {{0,0,-3}, {0,0,-2}, {0,1,-1}}}; //判连通是用到的， 预处理一下，方便找出每个小格子相邻的格子 struct node { int state, step; node(){} node(int s, int st):state(s), step(st){} }; void printMat() { for(int i = 0; i < N; ++i) { for(int j = 0; j < N; ++j) cout << g[i][j] << ' ' ; cout << endl; } } void gToA()//将g保存在数组a { int t = 0; for(int i = 0; i < N; ++i) for(int j = 0; j < N; ++j) a[t++] = g[i][j]; } void aToG()//将数组a转化为矩阵 { int t = 0; for(int i = 0; i < N; ++i) for(int j = 0; j < N; ++j) g[i][j] = a[t++]; } int pack()//利用康托展开哈希 { int ans = 0; gToA(); for(int i = 0; i < 9; ++i) { int t = 0; for(int j = i + 1; j < 9; ++j) if(a[j] < a[i]) ++t; ans += t * cantor[8 - i]; } return ans; } void unpack(int s)//将状态还原 { char p[10] = {0}; for(int i = 0; i < 9; ++i) { int t = s / cantor[8 - i], j; for(j = 0; j < 9; ++j) if(!p[j]) { if(t == 0) break; --t; } a[i] = j; p[j] = 1; s %= cantor[8 - i]; } aToG(); return ; } bool mark[N][N][4];//标记每个格子上的小三角 void dfs(int i, int j, int m, int color) { mark[i][j][m] = true; for(int k = 0; k < 3; ++k) { int xi = i + dir[m][k][0], yi = j + dir[m][k][1], t = m + dir[m][k][2]; if( xi < 0 || xi >= N || yi < 0 || yi >= N || p[g[xi][yi]].a[t] != color) continue; if(mark[xi][yi][t]) continue; dfs(xi, yi, t, color); } } bool check()//判断是否连通 { bool colorV[4] = {0}; memset(mark, false, sizeof(mark)); for(int i = 0; i < N; ++i) for(int j = 0; j < N; ++j) { for(int m = 0; m < 4; ++m) { if(mark[i][j][m]) continue; int color = p[g[i][j]].a[m]; if(colorV[color]) return false;//若同一个颜色存在俩个连通分量，则不符合 colorV[color] = true; dfs(i, j, m, color); } } return true; } void shitRowL(int r) { int tmp = g[r][0]; g[r][0] = g[r][1]; g[r][1] = g[r][2]; g[r][2] = tmp; } void shitRowR(int r) { int tmp = g[r][2]; g[r][2] = g[r][1]; g[r][1] = g[r][0]; g[r][0] = tmp; } void shitColU(int c) { int tmp = g[0][c]; g[0][c] = g[1][c]; g[1][c] = g[2][c]; g[2][c] = tmp; } void shitColD(int c) { int tmp = g[2][c]; g[2][c] = g[1][c]; g[1][c] = g[0][c]; g[0][c] = tmp; } queue<node> Q; void addNode(int s, int st) { if(!vis[s]) { Q.push(node(s, st)); vis[s] = true; } } int BFS(int s) { memset(vis,false,sizeof(vis)); vis[s] = true; while(!Q.empty()) Q.pop(); Q.push(node(s, 0)); while(!Q.empty()) { node cur = Q.front(); Q.pop(); unpack(cur.state); //printMat(); if(check()) return cur.step; for(int i = 0; i < 3; ++i) { if(row[i]) { shitRowL(i); int s = pack(); shitRowR(i); addNode(s, cur.step + 1); shitRowR(i); s = pack(); shitRowL(i); addNode(s, cur.step + 1); } if(col[i]) { shitColD(i); s = pack(); shitColU(i); addNode(s, cur.step + 1); shitColU(i); s = pack(); shitColD(i); addNode(s, cur.step + 1); } } } return -1; } int main() { int T, cas = 0; scanf("%d",&T); while(T--) { int t = 0; for(int i = 0; i < N; ++i) { row[i] = col[i] = true; for(int j = 0;j < N; ++j) { scanf("%s",str); for(int k = 0; k < 4; ++k) { if(str[k] == 'R') p[t].a[k] = 0; else if(str[k] == 'G') p[t].a[k] = 1; else if(str[k] == 'B') p[t].a[k] = 2; else p[t].a[k] = 3; } g[i][j] = t++; if(str[4] == '1') col[j] = row[i] = false; } } printf("Case #%d: %d\n", ++cas, BFS(0)); } return 0; }