HDU 无题I (IDA*)

无题I

Time Limit : 10000/10000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 16 Accepted Submission(s) : 8

Problem Description

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

2
1 2 3 4 1 2 3 4 1 2 3 4 2 3 4 1
4 1 1 1 1 2 2 2 2 3 3 3 3 4 4 4

Sample Output

1 1

Source

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

有16种变化，但是是有规律的，不需要一一列出。每次变化改变4个位置，估价函数是，最少的可能不满足要求的个数+3/4和上题有点像。

跑进了2s内，还不错，不知道31ms是怎么写的。

其中IDA*搜索的时候还是用到了父节点优化，比如上一步是第一列向上，那么下一步不会做第一列向下。

#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

const int INF=0x3f3f3f3f;

int a[4][4];
int depth,flag;

void change(int b[4][4],int k){
    if(k<8){
        if(k&1){
            int tmp=b[0][k/2];
            for(int i=1;i<4;i++)
                b[i-1][k/2]=b[i][k/2];
            b[3][k/2]=tmp;
        }else{
            int tmp=b[3][k/2];
            for(int i=3;i>0;i--)
                b[i][k/2]=b[i-1][k/2];
            b[0][k/2]=tmp;
        }
    }else{
        if(k&1){
            int tmp=b[(k-8)/2][0];
            for(int j=1;j<4;j++)
                b[(k-8)/2][j-1]=b[(k-8)/2][j];
            b[(k-8)/2][3]=tmp;
        }else{
            int tmp=b[(k-8)/2][3];
            for(int j=3;j>0;j--)
                b[(k-8)/2][j]=b[(k-8)/2][j-1];
            b[(k-8)/2][0]=tmp;
        }
    }
}

int H(int b[4][4]){
    int ans=INF,tmp=0;
    int flag[5],cnt;
    for(int i=0;i<4;i++){
        cnt=4;
        memset(flag,0,sizeof(flag));
        for(int j=0;j<4;j++)
            if(!flag[b[i][j]]){
                cnt--;
                flag[b[i][j]]=1;
            }
        tmp+=3-cnt;
    }
    ans=min(ans,tmp);
    tmp=0;
    for(int j=0;j<4;j++){
        cnt=4;
        memset(flag,0,sizeof(flag));
        for(int i=0;i<4;i++)
            if(!flag[b[i][j]]){
                cnt--;
                flag[b[i][j]]=1;
            }
        tmp+=3-cnt;
    }
    ans=min(ans,tmp);
    return (ans+3)/4;  //这里不理解
}

void IDAstar(int b[4][4],int curDepth,int dir){
    if(flag)
        return ;
    if(H(b)>curDepth)
        return ;
    if(curDepth==0){
        flag=1;
        return ;
    }
    for(int i=0;i<16;i++){
        if(dir!=-1 && dir/2==i/2 && (dir%2)^(i%2))  //上一步是第一列向上，那么下一步不会做第一列向下
            continue;
        int tmp[4][4];
        for(int j=0;j<4;j++)
            for(int k=0;k<4;k++)
                tmp[j][k]=b[j][k];
        change(tmp,i);
        IDAstar(tmp,curDepth-1,i);
    }
}

int main(){

    //freopen("input.txt","r",stdin);

    int t;
    scanf("%d",&t);
    while(t--){
        int i,j;
        for(i=0;i<4;i++)
            for(j=0;j<4;j++)
                scanf("%d",&a[i][j]);
        flag=0;
        for(depth=0;depth<=5;depth++){
            IDAstar(a,depth,-1);
            if(flag){
                printf("%d\n",depth);
                break;
            }
        }
        if(!flag)
            printf("-1\n");
    }
    return 0;
}