这道题最恶心的地方就是预处理了。辣鸡xcode都没法完整读入整张图(可能是没配置好)，必须文件输入。 预处理的时候将每一块拼图旋转4次，和结果对比，获取哪几个旋转的情况满足条件，这样就将问题抽象化。 旋转的时候要用dfs或者bfs看那几块会跟着一起转。一开始写的时候犯二了先改变了当前块的状态再去找其他块，连样例都过不去（也还好连样例都过不去，不然debug起来真的恶心）。 总的可能性总数为4^9，不算太大，直接bfs就好了。
#include<iostream> #include<string> #include<cstdio> #include<set> #include<stack> #include<list> #include<vector> #include<queue> #include<algorithm> #include<cstring> #include<cmath> #include<fstream> using namespace std; typedef long long ll; const int xx[] = {0,-1,0,1}; const int yy[] = {-1,0,1,0}; char st[10][10][10]; char ed[10][10][10]; int edge[10][5]; int fl[10][5]; int turn[10]; bool vis2[10]; bool vis[1111111]; //ifstream cin; //ofstream cout; int gethash(){ int t = 0; for(int i = 0;i < 9;++i){ t = t * 4 + turn[i]; } return t; } void getturn(int hash){ for(int i = 8;i >= 0;--i){ turn[i] = hash % 4; hash /= 4; } } inline int op(int x){ while (x >= 4) x -= 4; while (x < 0) x += 4; return x; } inline bool candfs(int a,int b,int k)//判断是否咬合 { if (edge[a][op(k - turn[a])] && edge[b][op(k + 2 - turn[b])]) return true; return false; } void dfs(int x,int flag){//传递旋转 vis2[x] = 1; for(int k = 0;k < 4;++k){ int i = x / 3 + xx[k],j = x % 3 + yy[k]; if (i < 0 || i > 2 || j < 0 || j > 2 || !candfs(x,i * 3 + j,k) || vis2[i * 3 + j]) continue; dfs(i * 3 + j,-flag); } turn[x] += flag;//一定要先dfs再修改拼图的状态！在这里wa了一次 turn[x] = op(turn[x]); } bool check(int hash){//判断是否满足结束条件 getturn(hash); for(int i = 0;i < 9;++i){ if (!fl[i][turn[i]]) return false; } return true; } void bfs(){ memset(vis,0,sizeof vis); vis[0] = 1; memset(turn,0,sizeof turn); queue<pair<int,int> > Q; Q.push({0,0}); while(!Q.empty()){ int x = Q.front().first,s = Q.front().second;Q.pop(); if (check(x)){ cout << s << endl; return; } for(int i = 0;i < 9;++i){ getturn(x); memset(vis2,0,sizeof vis2); dfs(i,1); int p = gethash(); if (vis[p]) continue; vis[p] = 1; Q.push({p,s+1}); } } cout << -1 << endl; } void cal(int k){//获取结束条件 char tmp[10][10],tmp2[10][10]; for(int i = 0;i < 8;++i) for(int j = 0;j < 8;++j) tmp[i][j] = st[k][i][j]; for(int t = 0;t < 4;++t){ bool b = true; for(int i = 0;i < 8;++i) for(int j = 0;j < 8;++j) if (tmp[i][j] != ed[k][i][j]) b = false; if (b) fl[k][t] = 1; for(int i = 0;i < 8;++i) for(int j = 0;j < 8;++j) tmp2[j][7-i] = tmp[i][j]; for(int i = 0;i < 8;++i) for(int j = 0;j < 8;++j) tmp[i][j] = tmp2[i][j]; } } void init(){ memset(fl,0,sizeof fl); for(int t = 0;t <= 6;t += 3) { for(int i = 0;i < 8;i++) { for(int k = t;k < t+3;k++) { cin >> st[k][i]; } } } for(int t = 0;t <= 6;t += 3) { for(int i = 0;i < 8;i++) { for(int k = t;k < t+3;k++) { cin >> ed[k][i]; } } } for(int i = 0;i < 9;i++) { for(int j = 0;j < 4;j++) { cin >> edge[i][j]; } } for(int k = 0;k < 9;k++) cal(k); if (check(0)) cout << 0 << endl; else bfs(); } int main(){ //cin.open("in.txt"); //cout.open("out.txt"); int t; cin >> t; while(t--){ init(); } }