HDU2234 无题I 题解 迭代加深搜索

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2234

题目大意：

一天机器人小A在玩一个简单的智力游戏，这个游戏是这样的，在一个4*4的矩阵中分别有4个1，4个2，4个3和4个4分别表示4种不同的东西，每一步小A可以把同一行的4个数往左移或者往右移一步或者把同一列的4个数字往上移或者往下移一步(1,2,3,4往左移后是2,3,4,1)，小A现在想知道进过最少的几步移动可以将矩阵的每行上的4个数字都一样或者每列上的4个数字都一样。但是小A又不想走太多步，他只要知道最少步数是否少于等于5步，是的话输出准确的步数，否则输出-1。

解题思路：迭代加深搜索。

示例代码：

#include <bits/stdc++.h>
using namespace std;
int a[4][4];
void l_rot(int r) {
    int t = a[r][0];
    a[r][0] = a[r][1];
    a[r][1] = a[r][2];
    a[r][2] = a[r][3];
    a[r][3] = t;
}
void r_rot(int r) {
    int t = a[r][3];
    a[r][3] = a[r][2];
    a[r][2] = a[r][1];
    a[r][1] = a[r][0];
    a[r][0] = t;
}
void u_rot(int c) {
    int t = a[0][c];
    a[0][c] = a[1][c];
    a[1][c] = a[2][c];
    a[2][c] = a[3][c];
    a[3][c] = t;
}
void d_rot(int c) {
    int t = a[3][c];
    a[3][c] = a[2][c];
    a[2][c] = a[1][c];
    a[1][c] = a[0][c];
    a[0][c] = t;
}
bool chk_r(int r) {
    for (int i = 1; i < 4; i ++) if (a[r][0] != a[r][i]) return false;
    return true;
}
bool chk_c(int c) {
    for (int i = 1; i < 4; i ++) if (a[0][c] != a[i][c]) return false;
    return true;
}
bool check() {
    return chk_r(0) && chk_r(1) && chk_r(2) && chk_r(3) || chk_c(0) && chk_c(1) && chk_c(2) && chk_c(3);
}
int D;
bool dfs(int d) {
    if (d >= D) {
        return check();
    }
    for (int i = 0; i < 4; i ++) {
        l_rot(i);
        if (dfs(d+1)) return true;
        r_rot(i);
        r_rot(i);
        if (dfs(d+1)) return true;
        l_rot(i);
        u_rot(i);
        if (dfs(d+1)) return true;
        d_rot(i);
        d_rot(i);
        if (dfs(d+1)) return true;
        u_rot(i);
    }
    return false;
}
int solve() {
    for (D = 0; D <= 5; D ++) {
        if (dfs(0)) return D;
    }
    return -1;
}
int T;
int main() {
    scanf("%d", &T);
    while (T --) {
        for (int i = 0; i < 4; i ++) for (int j = 0; j < 4; j ++) scanf("%d", &a[i][j]);
        printf("%d
", solve());
    }
    return 0;
}