hdu 6341 Problem J. Let Sudoku Rotate

题目：点击打开链接
题意：给你一个T，表示案例数量，给次给4*4块的数独，其中每一块数独都是4*4且不重复的，每一块数独只能顺时针反转，求使得数独合法的最少翻转次数。 

分析：直接暴搜加上可行性剪枝和最优性剪枝即可。 数独的限制较强，可行性剪枝的效果很好。 对每一块数独从上到下，从左到右遍历，每遍历一块，判断是否合法，若不合法就旋转一次再判断。 判断过程如下图所示，假设我们现在搜到了红色块区域，我们要对每一条蓝线和绿线查找有没有相同的元素，若有，则红色块不合法，反之，搜索下一块。 

代码：

#pragma comment(linker, "/STACK:102400000,102400000")///手动扩栈
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<string>
#include<cstdio>
#include<bitset>
#include<vector>
#include<cmath>
#include<ctime>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<set>
#include<map>
using namespace std;
#define debug test
#define mst(ss,b) memset((ss),(b),sizeof(ss))
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define inf 0x3f3f3f3f
#define eps 1e-10
#define PI acos(-1.0)
typedef pair<int,int> PII;
const ll mod = 1e9+7;
const int N = 1e6+10;

ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
ll qp(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
int to[4][2]={{-1,0},{1,0},{0,-1},{0,1}};

int t,ans,g[20][20],vs[20];

int gn(char c) {
    if('0'<=c&&c<='9')  return c-'0';
    else return c-'A'+10;
}

int ck(int x,int y) {
    rep(i,4*x-3,4*x) {
        mst(vs,0);
        rep(j,1,4*y)
            if(vs[g[i][j]]) return 0;
            else vs[g[i][j]]++;
    }
    rep(j,4*y-3,4*y) {
        mst(vs,0);
        rep(i,1,4*x)
            if(vs[g[i][j]]) return 0;
            else vs[g[i][j]]++;
    }
    return 1;
}

void rt(int x,int y) {
    int tp[20][20];
    for(int i=1,p=4*y-3;i<=4;i++,p++)
        for(int j=1,q=4*x;j<=4;j++,q--)
            tp[i][j]=g[q][p];
    for(int i=1,p=4*x-3;i<=4;i++,p++)
        for(int j=1,q=4*y-3;j<=4;j++,q++)
            g[p][q]=tp[i][j];
}

void dfs(int x,int y,int ct) {
    if(x>4) {
        ans=min(ans,ct);
        return ;
    }
    if(ct>=ans) return ;
    for(int i=0;i<4;i++) {
        if(i) rt(x,y);
        if(ck(x,y)) {
            if(y==4) dfs(x+1,1,ct+i);
            else dfs(x,y+1,ct+i);
        }
    }
    rt(x,y);
}

int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--) {
        char c;
        rep(i,1,16)
            rep(j,1,16)
                cin>>c,g[i][j]=gn(c);
        ans=inf;
        dfs(1,1,0);
        cout<<ans<<endl;
    }
    return 0;
}

参考博客：https://blog.csdn.net/qq_41608020/article/details/81386947