HDU 2234 無題I

 

無題I

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

Total Submission(s) : 2 Accepted Submission(s) : 1

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

 

每次改變四個點狀態

預估四個都改變正確 則至少需要移動次數為 (ANS+3)/4;

 

 

#include 
#include 
#include 
#include 
#include 
#define inf 1<<30

using namespace std;

int get_h(int b[4][4]){
    int ans=inf,tmp=0;
    for(int i=0;i<4;i++){
        bool flag[5];
        int cnt=4;
        memset(flag,false,sizeof(flag));
        for(int j=0;j<4;j++)
            if(!flag[b[i][j]]){
                cnt--;
                flag[b[i][j]]=true;
            }
        tmp+=3-cnt;
    }
    ans=min(tmp,ans);
    tmp=0;
    for(int j=0;j<4;j++){
        bool flag[5];
        int cnt=4;
        memset(flag,false,sizeof(flag));
        for(int i=0;i<4;i++)
            if(!flag[b[i][j]]){
                cnt--;
                flag[b[i][j]]=true;
            }
        tmp+=3-cnt;
    }
    ans=min(tmp,ans);
    return (ans+3)/4;
}

bool dfs(int len,int a[4][4],int kind,int kind1)
{
    if(get_h(a)>len) return false ;
    if(len==0) return true ;
    int aa[4][4];
    for(int i=0; i<4; i++)
    {
        if(kind==i&&kind1==2)
        {
            ;
        }
        else
        {
            for(int j=0; j<4; j++)
                for(int k=0; k<4; k++)
                    aa[j][k]=a[j][k];
            for(int j=0; j<4; j++)
                if(j) aa[i][j]=a[i][j-1];
                else aa[i][j]=a[i][3];
            if(dfs(len-1,aa,i,1)) return true ;
        }
        if(kind==i&&kind1==1)
            ;
        else
        {
            for(int j=0; j<4; j++)
                for(int k=0; k<4; k++)
                    aa[j][k]=a[j][k];
            for(int j=0; j<4; j++)
                if(j!=3) aa[i][j]=a[i][j+1];
                else aa[i][j]=a[i][0];
            if(dfs(len-1,aa,i,2)) return true ;
        }
        if(kind==i&&kind1==3)
        {
            ;
        }
        else
        {

            for(int j=0; j<4; j++)
                for(int k=0; k<4; k++)
                    aa[j][k]=a[j][k];
            for(int j=0; j<4; j++)
                if(j!=3) aa[j][i]=a[j+1][i];
                else aa[j][i]=a[0][i];
            if(dfs(len-1,aa,i,4)) return true ;
        }
        if(kind==i&&kind1==4)
        {
            ;
        }else
        {
            for(int j=0; j<4; j++)
                for(int k=0; k<4; k++)
                    aa[j][k]=a[j][k];
            for(int j=0; j<4; j++)
                if(j) aa[j][i]=a[j-1][i];
                else aa[j][i]=a[3][i];
            if(dfs(len-1,aa,i,3)) return true ;

        }
    }
    return false ;
}

int main()
{
    int t;
    scanf(%d,&t);
    while(t--)
    {
        int a[4][4];
        for(int i=0; i<4; i++)
        {
            for(int j=0; j<4; j++)
                scanf(%d,&a[i][j]);
        }
        int len;
        for(len=get_h(a); len<=5; len++)
        {
            if(dfs(len,a,-1,-1))
            {
                printf(%d
,len);
                break;
            }
        }
        if(len>5) printf(-1
);
    }
}