首页 > 代码库 > BNUOJ 6378 无题I

BNUOJ 6378 无题I

2024-07-15 12:30:57   224人阅读

无题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

21 2 3 41 2 3 41 2 3 42 3 4 14 1 1 11 2 2 22 3 3 33 4 4 4

Sample Output

11

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 long13 #define INF 0x3f3f3f3f14 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\n",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 long13 #define INF 0x3f3f3f3f14 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\n",ans<6?ans:-1);83     }84     return 0;85 }
View Code

 


联系
我们