BNUOJ 6378 无题I

无题I

Time Limit: 10000ms

Memory Limit: 32768KB

This problem will be judged on HDU. Original ID: 2234
64-bit integer IO format: %I64d Java class name: Main

一天机器人小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。

Input

先输入一个整数T，表示有T组数据。
对于每组数据输入4行，每行4列表示这个矩阵。

Output

对于每组输入输出一个正整数表示最少的移动步数，大于5则输出-1.

Sample Input

Sample Output

1
1

Source

HDOJ 2008 Summer Exercise（2）- Hold by Captain Xu

解题：IDA*

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <climits>
 7 #include <vector>
 8 #include <queue>
 9 #include <cstdlib>
10 #include <string>
11 #include <set>
12 #define LL long long
13 #define INF 0x3f3f3f3f
14 using namespace std;
15 int g[4][4],ans;
16 bool check(int (*t)[4]){
17     int i,j;
18     bool flag = false;
19     for(i = 0; i < 4; i++){
20         for(j = 1; j < 4; j++)
21         if(t[j][i] != t[j-1][i]) {flag = true;break;}//检查每一列
22         if(flag) break;
23     }
24     if(!flag) return true;
25     for(i = 0; i < 4; i++){
26         for(j = 1; j < 4; j++)
27         if(t[i][j] != t[i][j-1]) {flag = false;break;}
28         if(!flag) break;
29     }
30     return flag;
31 }
32 void shift(int (*t)[4],int dir,int u){
33     int i,temp;
34     if(dir == 0){//行左移
35         temp = t[u][0];
36         for(i = 0; i < 3; i++)
37             t[u][i] = t[u][i+1];
38         t[u][i] = temp;
39     }else if(dir == 1){//行右移
40         temp = t[u][3];
41         for(i = 3; i; i--)
42             t[u][i] = t[u][i-1];
43         t[u][i] = temp;
44     }else if(dir == 2){//列上移
45         temp = t[0][u];
46         for(i = 0; i < 3; i++)
47             t[i][u] = t[i+1][u];
48         t[i][u] = temp;
49     }else if(dir == 3){//列下移
50         temp = t[3][u];
51         for(i = 3; i; i--)
52             t[i][u] = t[i-1][u];
53         t[i][u] = temp;
54     }
55 }
56 
57 bool dfs(int (*t)[4],int step){
58     int mp[4][4],i,j,k;
59     if(ans == step && check(t)) return true;
60     if(ans <= step) return false;
61     for(i = 0; i < 4; i++){
62         for(j = 0; j < 4; j++){
63             memcpy(mp,t,sizeof(mp));
64             shift(mp,j,i);
65             if(dfs(mp,step+1)) return true;
66         }
67     }
68     return false;
69 }
70 int main(){
71     int ks,i,j;
72     scanf("%d",&ks);
73     while(ks--){
74         for(i = 0; i < 4; i++){
75             for(j = 0; j < 4; j++)
76                 scanf("%d",g[i]+j);
77         }
78         if(check(g)) {puts("0");continue;}
79         for(ans = 1; ans < 6; ans++)
80             if(dfs(g,0)) break;
81         printf("%d
",ans<6?ans:-1);
82     }
83     return 0;
84 }

View Code

优化了下，效果不明显啊！

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <climits>
 7 #include <vector>
 8 #include <queue>
 9 #include <cstdlib>
10 #include <string>
11 #include <set>
12 #define LL long long
13 #define INF 0x3f3f3f3f
14 using namespace std;
15 int g[4][4],ans;
16 bool check(int (*t)[4]){
17     int i,j;
18     bool flag = false;
19     for(i = 0; i < 4; i++){
20         for(j = 1; j < 4; j++)
21         if(t[j][i] != t[j-1][i]) {flag = true;break;}//检查每一列
22         if(flag) break;
23     }
24     if(!flag) return true;
25     for(i = 0; i < 4; i++){
26         for(j = 1; j < 4; j++)
27         if(t[i][j] != t[i][j-1]) {flag = false;break;}
28         if(!flag) break;
29     }
30     return flag;
31 }
32 void shift(int (*t)[4],int dir,int u){
33     int i,temp;
34     if(dir == 0){//行左移
35         temp = t[u][0];
36         for(i = 0; i < 3; i++)
37             t[u][i] = t[u][i+1];
38         t[u][i] = temp;
39     }else if(dir == 3){//行右移
40         temp = t[u][3];
41         for(i = 3; i; i--)
42             t[u][i] = t[u][i-1];
43         t[u][i] = temp;
44     }else if(dir == 1){//列上移
45         temp = t[0][u];
46         for(i = 0; i < 3; i++)
47             t[i][u] = t[i+1][u];
48         t[i][u] = temp;
49     }else if(dir == 2){//列下移
50         temp = t[3][u];
51         for(i = 3; i; i--)
52             t[i][u] = t[i-1][u];
53         t[i][u] = temp;
54     }
55 }
56 
57 bool dfs(int (*t)[4],int step,int pre,int dir){
58     int mp[4][4],i,j,k;
59     if(ans == step && check(t)) return true;
60     if(ans <= step) return false;
61     for(i = 0; i < 4; i++){
62         for(j = 0; j < 4; j++){
63             memcpy(mp,t,sizeof(mp));
64             if(i == pre && j == dir) continue;
65             shift(mp,j,i);
66             if(dfs(mp,step+1,i,3-j)) return true;
67         }
68     }
69     return false;
70 }
71 int main(){
72     int ks,i,j;
73     scanf("%d",&ks);
74     while(ks--){
75         for(i = 0; i < 4; i++){
76             for(j = 0; j < 4; j++)
77                 scanf("%d",g[i]+j);
78         }
79         if(check(g)) {puts("0");continue;}
80         for(ans = 1; ans < 6; ans++)
81             if(dfs(g,0,-1,-1)) break;
82         printf("%d
",ans<6?ans:-1);
83     }
84     return 0;
85 }

View Code