题目传送门

题意：

给你16个16宫格的数独，里面是0~F，你可以逆时针旋转里面的每个16宫格

问你它是从标准数独逆时针旋转多少次得到？

思路：

可以知道每个16宫已经是标准的了，接下来只要考虑每行、每列就行了

那么我们在dfs中就可以用两个行列两个数组来标记每个数字出现的次数，

大于1则不行

另外此时是逆时针来的，那么你就要顺时针回去

逆一次等于顺3次

参考博客：https://www.cnblogs.com/zquzjx/p/10326048.html

代码：

#include<bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define N 25

int g[N][N],G[N][N];

int R[N][N],C[N][N];

int ans;

int get(int x,int y,int I,int J,int k)

{

    if(k==) return g[y+-J+][x+I];

    else if(k==) return g[x+-I+][y+-J+];

    else if(k==) return g[x][y+-I+];

    else return g[x+I][y+J];

}

bool Rotate(int x,int y,int k)

{

    bool flag=;

    for(int i=;i<;i++)

    {

        for(int j=;j<;j++)

        {

            int xx=(x-)*+i;

            int yy=(y-)*+j;

            G[xx][yy]=get(xx,yy,i,j,k);//cout<<xx<<" "<<yy<<" "<<G[xx][yy]<<endl;

           // cout<<(x-1)*4+i<<" "<<(y-1)*4+j<<endl;

            int r=++R[xx][G[xx][yy]];

            int l=++C[yy][G[xx][yy]];

            if(r>||l>) flag=;

        }

    }

    return flag;

}

void reRotate(int x,int y)

{

    for(int i=;i<;i++)

    {

        for(int j=;j<;j++)

        {

            int xx=(x-)*+i;

            int yy=(y-)*+j;

            --R[xx][G[xx][yy]];

            --C[yy][G[xx][yy]];

            G[xx][yy]=g[xx][yy];

        }

    }

}

void dfs(int x,int y,int sum)

{

    if(x==)

    {

        ans=min(ans,sum);

        return ;

    }

    for(int i=;i<=;i++)

    {

        if(!Rotate(x,y,i))

        {

            reRotate(x,y);

            continue;

        }

        if(y==) dfs(x+,,sum+i);

        else dfs(x,y+,sum+i);

        reRotate(x,y);

    }

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        char s[];

        for(int i=;i<=;i++)

        {

            scanf("%s",s+);

            for(int j=;j<=;j++)

            {

                if(s[j]>=''&&s[j]<='') g[i][j]=s[j]-''+;

                else g[i][j]=s[j]-'A'+;

            }

        }

        /*for(int i=1;i<=16;i++){

            for(int j=1;j<=16;j++)

             printf("%d",g[i][j]);

           cout<<endl;}*/

           memset(R,,sizeof(R));

           memset(C,,sizeof(C));

         ans=INF;

        dfs(,,);

        printf("%d\n",ans);

    }

    return ;

}

参考代码：

#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define LL long long

#define mem(i,j) memset(i,j,sizeof(i))

const int N=1e5+;

const int MOD=1e9+;

int G[][], g[][];

int R[][], C[][];

int ans;

#define w(i) (i-1)*4

#define wG(i,j,I,J) G[w(i)+I][w(j)+J]

int get(int r,int c,int x,int y,int k) {

    if(k==) return wG(r,c,-y+,x);

    else if(k==) return wG(r,c,-x+,-y+);

    else if(k==) return wG(r,c,y,-x+);

    else return wG(r,c,x,y);

}

// 得到在r,c的块内x,y位置在第k种旋转之后的新数值

bool Rotate(int i,int j,int k) {

    bool OK=;

    for(int I=;I<=;I++)

        for(int J=;J<=;J++) {

            int x=w(i)+I, y=w(j)+J;

            g[x][y]=get(i,j,I,J,k);

            int r=++R[x][g[x][y]];

            int c=++C[y][g[x][y]];

            if(r> || c>) OK=;

            // 这种旋转与之前其他块的旋转冲突

            // 继续发展下去得到的一定是错误的

        }

    return OK;

} // 旋转i,j块 方式为第k种

void reRotate(int i,int j) {

    for(int I=;I<=;I++)

        for(int J=;J<=;J++) {

            int x=w(i)+I, y=w(j)+J;

            --R[x][g[x][y]];

            --C[y][g[x][y]];

            g[x][y]=G[x][y];

        }

} // 将i,j块的旋转取消

void dfs(int x,int y,int sum) {

    if(sum>ans) return;

    if(x==) {

        ans=min(ans,sum);

        return;

    } // 四行四列16个块 到第五行说明已枚举了所有块的旋转

    for(int i=;i<=;i++) {

        if(Rotate(x,y,i)==) {

            reRotate(x,y); continue;

        } // 若发现这种旋转方式会冲突就跳过

        if(y==) dfs(x+,,sum+i);

        else dfs(x,y+,sum+i);

        reRotate(x,y);

    }

} // 搜索枚举16个块的旋转方式

int main()

{

    int t; scanf("%d",&t);

    while(t--) {

        for(int i=;i<=;i++) {

            char s[]; scanf("%s",s);

            for(int j=;j<;j++) {

                if(s[j]>='' && s[j]<='')

                    G[i][j+]=s[j]-'';

                else G[i][j+]=s[j]-'A'+;

            }

        }

        mem(R,); mem(C,);

        ans=INF; dfs(,,);

        printf("%d\n",ans);

    }

    return ;

}

巴特西

hdu6341 Problem J. Let Sudoku Rotate （dfs）

题目传送门

最新文章

热门文章