bryce1010专题训练——搜索+剪枝

bryce1010模板

搜索+剪枝题集：https://vjudge.net/contest/243461

1、DFS+剪枝
hdu 6341 Problem J. Let Sudoku Rotate
http://acm.hdu.edu.cn/showproblem.php?pid=6341
题意：问你最少多少次旋转图中的4*4矩阵能还原成正确的大矩阵。
虽然时间复杂度理论上过不了，但是剪枝后可以过。

#include<bits/stdc++.h>
using namespace std;
const int MOD=1e9+7;
typedef long long ll;
char s[20][20];
char p[5][5];
int vis[20];
void roat(int x,int y)//顺时针旋转矩阵90度
{
    for(int i=1,a=y;i<=4;i++,a++)
    for(int j=1,b=x;j<=4;j++,b--)p[i][j]=s[b][a];
    for(int j=1,a=y;j<=4;j++,a++)
    for(int i=4,b=x;i>=1;i--,b--)s[b][a]=p[i][j];
}
int g(char c){return (c>='0'&&c<='9')?c-'0':c-'A'+10;}
int checkrow(int x)
{
    for(int i=x-3;i<=x;i++)//每行数的和要等于120
    {
        int sum=0;
        for(int j=1;j<=16;j++)sum+=g(s[i][j]);
        if(sum!=120)return 0;
    }
    for(int i=x-3;i<=x;i++)//每行不能有重复出现的数
    {
        memset(vis,0,sizeof vis);
        for(int j=1;j<=16;j++)
        {
            if(vis[g(s[i][j])])return 0;
            vis[g(s[i][j])]=1;
        }
    }
    for(int j=1;j<=16;j++)//每列不能有重复出现的数
    {
        memset(vis,0,sizeof vis);
        for(int i=1;i<=x;i++)
        {
            if(vis[g(s[i][j])])return 0;
            vis[g(s[i][j])]=1;
        }
    }
    return 1;
}
int ans;
void dfs(int k,int num)//k表示枚举到第k行，num表示旋转次数
{
    if(num>ans)return;
    if(k==20){ans=min(ans,num);return;}
    for(int a=0;a<=3;a++,roat(k,1))//枚举这4个子矩阵的旋转次数
    for(int b=0;b<=3;b++,roat(k,5))
    for(int c=0;c<=3;c++,roat(k,9))
    for(int d=0;d<=3;d++,roat(k,13))
    {
        if(checkrow(k)==0)continue;//判断前k行是否满足数独的条件
        dfs(k+4,num+a+b+c+d);
    }
}
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        for(int i=1;i<=16;i++)scanf("%s",s[i]+1);
        ans=16*4;
        dfs(4,0);
        printf("%d\n",ans);
    }
    return 0;
}