HDU 2234 IDA*

無題I

Time Limit: 10000/10000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1648????Accepted Submission(s): 640

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

#include <iostream>
#include <cstring>
using namespace std;
int num[4][4],h;
int check(){
    int flag=0;
    for(int i=0;i<4;i++){
        for(int j=1;j<4;j++){
            if(num[i][j]!=num[i][0]){
                flag=1;
                break;
            }
        }
        if(flag){
            for(int j=1;j<4;j++){
                if(num[j][i]!=num[0][i]){
                    return 0;
                }
            }
        }
    }
    return 1;
}

void up(int i){
    int t;
    t=num[0][i];
    for(int j=0;j<3;j++){
        num[j][i]=num[j+1][i];
    }
    num[3][i]=t;
}

void down(int i){
    int t;
    t=num[3][i];
    for(int j=3;j>0;j--){
        num[j][i]=num[j-1][i];
    }
    num[0][i]=t;
}

void left(int i){
    int t;
    t=num[i][0];
    for(int j=0;j<3;j++){
        num[i][j]=num[i][j+1];
    }
    num[i][3]=t;
}

void right(int i){
    int t;
    t=num[i][3];
    for(int j=3;j>0;j--){
        num[i][j]=num[i][j-1];
    }
    num[i][0]=t;
}

int get_h(){
    int s1=0,s2=0,ans;
    int a[5];
    for(int i=0;i<4;i++){
        memset(a,0,sizeof(a));
        ans=0;
        for(int j=0;j<4;j++){
            a[num[i][j]]=1;
        }
        for(int j=1;j<=4;j++){
            ans+=a[j];
        }
        s1=max(s1,ans-1); 
    }
    for(int j=0;j<4;j++){
        memset(a,0,sizeof(a));
        ans=0;
        for(int i=0;i<4;i++){
            a[num[i][j]]=1;
        }
        for(int i=1;i<=4;i++){
            ans+=a[i];
        }
        s2=max(s2,ans-1); 
    }
    return min(s1,s2);
}

int IDA(int ans){
    if(ans==h){
        return check();
    }
    if(ans+get_h()>h){
        return 0;
    }
    for(int i=0;i<4;i++){
        left(i);
        if(IDA(ans+1)){
            return 1;
        }
        right(i);//還原
        right(i);
        if(IDA(ans+1)){
            return 1;
        }
        left(i);//還原
    }
    for(int i=0;i<4;i++){
        up(i);
        if(IDA(ans+1)){
            return 1;
        }
        down(i);//還原
        down(i);
        if(IDA(ans+1)){
            return 1;
        }
        up(i);//還原
    }
    return 0;
}

int main(){
    cin.sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--){
        for(int i=0;i<4;i++){
            for(int j=0;j<4;j++){
                cin>>num[i][j];
            }
        }
        if(check()){
            cout<<"0"<<endl;
        }
        else{
            h=1;
            while(h<=5){
                if(IDA(0)){
                    break;
                }
                h++;
            }
            if(h<=5){
                cout<<h<<endl;
            }
            else{
                cout<<"-1"<<endl;
            }
        }
    }
    return 0;
}

?

2016-12-05 16:24:07