HDU 6341 Let Sudoku Rotate（搜索）

题目链接：Let Sudoku Rotate

题意

有一个 16×16$16\times 16$ 的数独，其中的每一行、每一列、每一 4×4$4\times 4$ 的方格内都不重复地包含 0$0$ 到 F$F$ 的每一个十六进制数，Kazari$Kazari$ 已经完成了一个数独，但是被 Minato$Minato$ 逆时针旋转了其中的某几个 4×4$4\times 4$ 的方格，给出旋转后的方格，问最少需要几步才能从原数独逆时针旋转到当前状态。

输入

第一行为一个整数 T (1≤T≤103)$T(1\le T\le {10}^3)$，接下来有 T$T$ 组数据，每组数据为一个 16×16$16\times 16$ 的字符矩阵，矩阵中只包含 ′0′${}^{\prime }{0}^{\prime }$ 到 ′9′${}^{\prime }{9}^{\prime }$ 以及 ′A′${}^{\prime }{A}^{\prime }$ 到 ′F′${}^{\prime }{F}^{\prime }$ 这 16$16$ 种字符，表示最终的数独状态。

输出

输出一个非负整数，表示最少需要的操作次数。

样例

输入

1
681D5A0C9FDBB2F7
0A734B62E167D9E5
5C9B73EF3C208410
F24ED18948A5CA63
39FAED5616400B74
D120C4B7CA3DEF38
7EC829A085BE6D51
B56438F129F79C2A
5C7FBC4E3D08719F
AE8B1673BF42A58D
60D3AF25619C30BE
294190D8EA57264C
C7D1B35606835EAB
AF52A1E019BE4306
8B36DC78D425F7C9
E409492FC7FA18D2

输出

5

提示

原数独按照如下方式旋转可以得到所输入的数独：

题解

将每个 4×4$4\times 4$ 格子顺时针旋转，每次旋转检查是否与当前格子左上方的所有格子冲突，若冲突则剪枝，否则继续往下搜索，“由于数独限制较强，剪枝效果良好。”

过题代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cstring>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <algorithm>
#include <sstream>
using namespace std;

#define LL long long
const int maxn = 100;
int T, cnt, ans;
int num[maxn][maxn], Copy[maxn][maxn];
char str[maxn][maxn];
int vis[20];

void Print() {
    for(int i = 0; i < 16; ++i) {
        for(int j = 0; j < 16; ++j) {
            printf("%3d", num[i][j]);
        }
        printf("\n");
    }
}

void rot(int x, int y) {
    for(int i = 0; i < 4; ++i) {
        for(int j = 0; j < 4; ++j) {
            Copy[x + j][y + 3 - i] = num[x + i][y + j];
        }
    }
    for(int i = 0; i < 4; ++i) {
        for(int j = 0; j < 4; ++j) {
            num[x + i][y + j] = Copy[x + i][y + j];
        }
    }
}

bool Check(int x, int y) {
    for(int i = x; i < x + 4; ++i) {
        ++cnt;
        for(int j = 0; j < y + 4; ++j) {
            if(vis[num[i][j]] == cnt) {
                return false;
            }
            vis[num[i][j]] = cnt;
        }
    }
    for(int j = y; j < y + 4; ++j) {
        ++cnt;
        for(int i = 0; i < x + 4; ++i) {
            if(vis[num[i][j]] == cnt) {
                return false;
            }
            vis[num[i][j]] = cnt;
        }
    }
    return true;
}

void dfs(int depth, int step) {
    if(depth == 16) {
        ans = min(ans, step);
        return ;
    }
    int x = depth / 4;
    int y = depth % 4;
    for(int i = 0; i < 4; ++i) {
        if(Check(x * 4, y * 4)) {
            dfs(depth + 1, step + i);
        }
        rot(x * 4, y * 4);
    }
}

int main() {
    #ifdef Dmaxiya
    freopen("test.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    #endif // Dmaxiya
    ios::sync_with_stdio(false);

    scanf("%d", &T);
    while(T--) {
        for(int i = 0; i < 16; ++i) {
            scanf("%s", str[i]);
            for(int j = 0; j < 16; ++j) {
                if(str[i][j] <= '9') {
                    num[i][j] = str[i][j] - '0';
                } else {
                    num[i][j] = str[i][j] - 'A' + 10;
                }
            }
        }
        ans = INT_MAX;
        dfs(0, 0);
        printf("%d\n", ans);
    }

    return 0;
}