I - Problem J. Let Sudoku Rotate

题意：
给一个16*16的数独，每个4*4的子模块都有可能被逆时针转动过，问至少转动了多少次。
题解：
dfs枚举每一行的四个4*4的子模块的转动次数，在进行数独判断剪枝。

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 20;
char s[maxn][maxn];
int sudu[maxn][maxn], ans;
int vis[maxn];
void rot(int x, int y)
{
    int t[5][5];
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++)
            t[j][3 - i] = sudu[x + i][y + j];
    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 4; j++)
            sudu[x + i][y + j] = t[i][j];
}
int check(int x, int y)
{
    for (int i = x; i < x + 4; i++)
    {
        memset(vis, 0, sizeof(vis));
        for (int j = 0; j < y + 4; j++)
        {
            vis[sudu[i][j]]++;
            if (vis[sudu[i][j]] >= 2)
                return 0;
        }
    }
    for (int i = y; i < y + 4; i++)
    {
        memset(vis, 0, sizeof(vis));
        for (int j = 0; j < x + 4; j++)
        {
            vis[sudu[j][i]]++;
            if (vis[sudu[j][i]] >= 2)
                return 0;
        }
    }
    return 1;
}
void dfs(int i, int j, int step)
{
    if (i == 4)
    {
        ans = min(ans, step);
        return;
    }
    if (step >= ans)
        return;
    if (j == 4)
        dfs(i + 1, 0, step);
    for (int t = 0; t < 4; t++)
    {
        if (check(i * 4, j * 4)) 
            dfs(i, j + 1, step + t);
        rot(i * 4, j * 4);
    }
}
void solve()
{
    for (int i = 0; i < 16; i++)
    {
        cin >> s[i];
        for (int j = 0; j < 16; j++)
        {
            if (isdigit(s[i][j]))
                sudu[i][j] = s[i][j] - '0';
            else
                sudu[i][j] = s[i][j] - 'A' + 10;
        }
    }
    ans = 16 * 4;
    dfs(0, 0, 0);
    cout << ans << endl;
}
int main()
{
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}