?
无题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 ); } }
?
?