（IDA*）HDU

题意：有一个4*4的矩阵，每次可以让某一行向左或向右滚动一次，或者让某一列向上或向下滚动一次，问在5次之内要几次能使矩阵达到每行的数字都相同或者每列的数字都相同，如果超过5次，就输出-1。

分析：第一次学A*和IDA*，看这题是中文题就先写了这题，一开始是用A*写的，然后写的很蛋疼。之后发现也就5次，直接使用IDA*就行了，折腾了一下，算是AC了。但是跑了6000ms+。

因为之前加了前后判重，就是说来回滚动，去掉之后变成了4000ms+。

后来百度了一些大佬的博客，发现我的状态扩展写的很挫。都是新开局部图，然后继续递归，其实只需要dfs中普通的回溯就行了。。

比如一行向右滚动了，之后再回溯就好了，其实还是自己把IDA*看的太复杂，之后和学长交流一下。

他说在他眼里A*和IDA*其实就是bfs和dfs，只不过是加了评估函数来剪枝的，感觉好牛逼哦。

代码：

4000ms+：

  1 #include <set>
  2 #include <map>
  3 #include <list>
  4 #include <cmath>
  5 #include <queue>
  6 #include <vector>
  7 #include <bitset>
  8 #include <string>
  9 #include <cctype>
 10 #include <cstdio>
 11 #include <cstring>
 12 #include <cstdlib>
 13 #include <iostream>
 14 #include <algorithm>
 15 
 16 using namespace std;
 17 
 18 typedef long long ll;
 19 typedef unsigned long long ull;
 20 #define inf (0x3f3f3f3f)
 21 #define lnf (0x3f3f3f3f3f3f3f3f)
 22 #define eps (1e-8)
 23 int sgn(double a) {return a < -eps ? -1 : a < eps ? 0 : 1;}
 24 
 25 //--------------------------
 26 
 27 
 28 
 29 char maps[4][4];
 30 
 31 
 32 int t;
 33 int maxh;
 34 
 35 bool check(char ss[][4]) {
 36     bool flag = true;
 37     for (int i = 0; i < 4; i++) {
 38         if (ss[i][0] != ss[i][1] || ss[i][1] != ss[i][2] || ss[i][2] != ss[i][3]) {
 39             flag = false;
 40         }
 41     }
 42     if (flag)return true;
 43     flag = true;
 44     for (int i = 0; i < 4; i++) {
 45         if (ss[0][i] != ss[1][i] || ss[1][i] != ss[2][i] || ss[2][i] != ss[3][i]) {
 46             flag = false;
 47         }
 48     }
 49     return flag;
 50 }
 51 
 52 ll gethash(char ss[][4]) {
 53 
 54     ll res = 0;
 55     for (int i = 0; i < 4; i++) {
 56         for (int j = 0; j < 4; j++) {
 57             res = res * 10 + ss[i][j] - '0';
 58         }
 59     }
 60     return res;
 61 }
 62 
 63 void clone(char tmp[][4], char ss[][4]) {
 64     for (int i = 0; i < 4; i++) {
 65         for (int j = 0; j < 4; j++) {
 66             tmp[i][j] = ss[i][j];
 67         }
 68     }
 69 
 70 }
 71 
 72 void debug(char ss[][4]) {
 73     for (int i = 0; i < 4; i++) {
 74         for (int j = 0; j < 4; j++) {
 75             printf("%c ", ss[i][j] );
 76         }
 77         puts("");
 78     }
 79     puts("");
 80 
 81 
 82 }
 83 
 84 bool dfs(char ss[][4], int depth) {
 85     if (depth >= maxh)return false;
 86     char temp[4][4];
 87 
 88     for (int i = 0; i < 4; i++) {
 89         clone(temp, ss);
 90         for (int j = 0; j < 4; j++) {
 91             temp[i][(j + 1) % 4] = ss[i][j];
 92         }
 93         ll thash = gethash(temp);
 94         if (check(temp))return true;
 95         if (dfs(temp, depth + 1))return true;
 96 
 97         clone(temp, ss);
 98         for (int j = 0; j < 4; j++) {
 99             temp[i][(j + 3) % 4] = ss[i][j];
100         }
101         thash = gethash(temp);
102         if (check(temp))return true;
103         if (dfs(temp, depth + 1))return true;
104 
105     }
106 
107     for (int j = 0; j < 4; j++) {
108         clone(temp, ss);
109         for (int i = 0; i < 4; i++) {
110             temp[(i + 1) % 4][j ] = ss[i][j];
111         }
112         ll thash = gethash(temp);
113         if (check(temp))return true;
114         if (dfs(temp, depth + 1))return true;
115 
116 
117         clone(temp, ss);
118         for (int i = 0; i < 4; i++) {
119             temp[(i + 3) % 4][j ] = ss[i][j];
120         }
121         thash = gethash(temp);
122         if (check(temp))return true;
123         if (dfs(temp, depth + 1))return true;
124 
125     }
126     return false;
127 }
128 
129 void solve() {
130 
131     scanf("%d", &t);
132     while (t--) {
133         int x;
134         maxh = 0;
135         bool flag = false;
136         for (int i = 0; i < 4; i++) {
137             for (int j = 0; j < 4; j++) {
138                 scanf("%d", &x);
139                 maps[i][j] = x + '0';
140             }
141         }
142         if (check(maps)) {
143             puts("0");
144         } else {
145             for (maxh = 1; maxh <= 5; maxh++) {
146                 if (dfs(maps, 0)) {
147                     flag = true;
148                     break;
149                 }
150             }
151         }
152         if (flag)printf("%d
", maxh );
153         else puts("-1");
154     }
155 
156 }
157 
158 
159 int main() {
160 
161 #ifndef ONLINE_JUDGE
162     freopen("1.in", "r", stdin);
163     //freopen("1.out", "w", stdout);
164 #endif
165     //iostream::sync_with_stdio(false);
166     solve();
167     return 0;
168 }