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

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

 

每次改变四个点状态

预估四个都改变正确 则至少需要移动次数为 (ANS+3)/4;

 

 

#include #include #include #include #include #define inf 1<<30using 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);
}
}