本文共 2160 字，大约阅读时间需要 7 分钟。
给一个由4*4个4*4的小格组成数独，这些数独是由一个块逆时针旋转得来的，所以要还原的话就模拟出顺时针的过程，先把里面的字母转化成数字，然后从第一个块开始枚举，每个dfs和之前枚举的已经满足条件的块，然后先枚举每一行的每块，这一行枚举完了去枚举下一行的状态，一直枚举到最后一块为止。
#include#include #include #include #include #include #include #include #include #include #include #include #include #define lowbit(x) (x & (-x))typedef unsigned long long int ull;typedef long long int ll;const double pi = 4.0*atan(1.0);const int inf = 0x3f3f3f3f;const int maxn = 1e5+10;const int maxm = 10000007;const int mod = 1e9+7;using namespace std;int n, m, tol, T;char s[20];int e[20][20];int t[20][20];bool vis[30];int ans;void init() { ans = inf; memset(e, 0, sizeof e); memset(t, 0, sizeof t);}void change(int x, int y) { memset(t, 0, sizeof t); for(int i1=4*x-3, j2=4*y-3; i1<=4*x; i1++, j2++) { for(int j1=4*y-3, i2=4*x; j1<=4*y; j1++, i2--) { t[i1][j1] = e[i2][j2]; } } for(int i=4*x-3; i<=4*x; i++) { for(int j=4*y-3; j<=4*y; j++) { e[i][j] = t[i][j]; } }}bool check(int x, int y) { for(int i=4*x-3; i<=4*x; i++) { memset(vis, 0, sizeof vis); for(int j=1; j<=4*y; j++) { if(vis[e[i][j]]) return false; vis[e[i][j]] = true; } } for(int j=4*y-3; j<=4*y; j++) { memset(vis, 0, sizeof vis); for(int i=1; i<=4*x; i++) { if(vis[e[i][j]]) return false; vis[e[i][j]] = true; } } return true;}void dfs(int x, int y, int cnt) { if(y>4) { ans = check(4, 4) ? min(ans, cnt) : ans; return ; } if(cnt > ans) return ; for(int i=0; i<4; i++) { if(i) change(x, y); if(!check(x, y)) continue; if(x == 4) dfs(1, y+1, cnt + i); else dfs(x+1, y, cnt + i); } change(x, y);}int main() { scanf("%d", &T); while(T--) { init(); char ch; for(int i=1; i<=16; i++) { scanf("%s", s+1); for(int j=1; j<=16; j++) { ch = s[j]; e[i][j] = isdigit(ch) ? ch - '0' : ch - 'A' + 10; } }// for(int i=1; i<=16; i++) for(int j=1; j<=16; j++) printf("%d%c", e[i][j], j==16 ? '\n' : ' ');// change(2, 1);// cout << endl;// for(int i=1; i<=16; i++) for(int j=1; j<=16; j++) printf("%d%c", e[i][j], j==16 ? '\n' : ' '); dfs(1, 1, 0); printf("%d\n", ans); } return 0;}
转载于:https://www.cnblogs.com/Jiaaaaaaaqi/p/9414821.html
