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*

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <climits>

 #include <vector>

 #include <queue>

 #include <cstdlib>

 #include <string>

 #include <set>

 #define LL long long

 #define INF 0x3f3f3f3f

 using namespace std;

 int g[][],ans;

 bool check(int (*t)[]){

     int i,j;

     bool flag = false;

     for(i = ; i < ; i++){

         for(j = ; j < ; j++)

         if(t[j][i] != t[j-][i]) {flag = true;break;}//检查每一列

         if(flag) break;

     }

     if(!flag) return true;

     for(i = ; i < ; i++){

         for(j = ; j < ; j++)

         if(t[i][j] != t[i][j-]) {flag = false;break;}

         if(!flag) break;

     }

     return flag;

 }

 void shift(int (*t)[],int dir,int u){

     int i,temp;

     if(dir == ){//行左移

         temp = t[u][];

         for(i = ; i < ; i++)

             t[u][i] = t[u][i+];

         t[u][i] = temp;

     }else if(dir == ){//行右移

         temp = t[u][];

         for(i = ; i; i--)

             t[u][i] = t[u][i-];

         t[u][i] = temp;

     }else if(dir == ){//列上移

         temp = t[][u];

         for(i = ; i < ; i++)

             t[i][u] = t[i+][u];

         t[i][u] = temp;

     }else if(dir == ){//列下移

         temp = t[][u];

         for(i = ; i; i--)

             t[i][u] = t[i-][u];

         t[i][u] = temp;

     }

 }

 bool dfs(int (*t)[],int step){

     int mp[][],i,j,k;

     if(ans == step && check(t)) return true;

     if(ans <= step) return false;

     for(i = ; i < ; i++){

         for(j = ; j < ; j++){

             memcpy(mp,t,sizeof(mp));

             shift(mp,j,i);

             if(dfs(mp,step+)) return true;

         }

     }

     return false;

 }

 int main(){

     int ks,i,j;

     scanf("%d",&ks);

     while(ks--){

         for(i = ; i < ; i++){

             for(j = ; j < ; j++)

                 scanf("%d",g[i]+j);

         }

         if(check(g)) {puts("");continue;}

         for(ans = ; ans < ; ans++)

             if(dfs(g,)) break;

         printf("%d\n",ans<?ans:-);

     }

     return ;

 }

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

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <climits>

 #include <vector>

 #include <queue>

 #include <cstdlib>

 #include <string>

 #include <set>

 #define LL long long

 #define INF 0x3f3f3f3f

 using namespace std;

 int g[][],ans;

 bool check(int (*t)[]){

     int i,j;

     bool flag = false;

     for(i = ; i < ; i++){

         for(j = ; j < ; j++)

         if(t[j][i] != t[j-][i]) {flag = true;break;}//检查每一列

         if(flag) break;

     }

     if(!flag) return true;

     for(i = ; i < ; i++){

         for(j = ; j < ; j++)

         if(t[i][j] != t[i][j-]) {flag = false;break;}

         if(!flag) break;

     }

     return flag;

 }

 void shift(int (*t)[],int dir,int u){

     int i,temp;

     if(dir == ){//行左移

         temp = t[u][];

         for(i = ; i < ; i++)

             t[u][i] = t[u][i+];

         t[u][i] = temp;

     }else if(dir == ){//行右移

         temp = t[u][];

         for(i = ; i; i--)

             t[u][i] = t[u][i-];

         t[u][i] = temp;

     }else if(dir == ){//列上移

         temp = t[][u];

         for(i = ; i < ; i++)

             t[i][u] = t[i+][u];

         t[i][u] = temp;

     }else if(dir == ){//列下移

         temp = t[][u];

         for(i = ; i; i--)

             t[i][u] = t[i-][u];

         t[i][u] = temp;

     }

 }

 bool dfs(int (*t)[],int step,int pre,int dir){

     int mp[][],i,j,k;

     if(ans == step && check(t)) return true;

     if(ans <= step) return false;

     for(i = ; i < ; i++){

         for(j = ; j < ; j++){

             memcpy(mp,t,sizeof(mp));

             if(i == pre && j == dir) continue;

             shift(mp,j,i);

             if(dfs(mp,step+,i,-j)) return true;

         }

     }

     return false;

 }

 int main(){

     int ks,i,j;

     scanf("%d",&ks);

     while(ks--){

         for(i = ; i < ; i++){

             for(j = ; j < ; j++)

                 scanf("%d",g[i]+j);

         }

         if(check(g)) {puts("");continue;}

         for(ans = ; ans < ; ans++)

             if(dfs(g,,-,-)) break;

         printf("%d\n",ans<?ans:-);

     }

     return ;

 }

巴特西