/* 比较简单的A* 估价函数很简单就是除了左上角的联通快之外的不同的个数 加上迭代 好像答案最多在16步之内出解 这样裸裸的交上去是50分 在考虑剪枝 每个选颜色的时候一定是选左上角联通快附近的颜色 处理一下只枚举这样的颜色 80 - 90 分了就 下面是代码 */ #include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,ans,g[9][9],a[9][9],tot,color,falg,f[9][9],vis[6],C; int xx[4]={0,0,-1,1}; int yy[4]={1,-1,0,0}; int init() { int x=0;char s=getchar(); while(s<'0'||s>'9')s=getchar(); while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x; } void Go(int x,int y,int c,int r) { a[x][y]=r;f[x][y]=1; for(int i=0;i<4;i++) { int nx=x+xx[i]; int ny=y+yy[i]; if(nx>0&&nx<=n&&ny>0&&ny<=n&&f[nx][ny]==0&&a[nx][ny]==c) Go(nx,ny,c,r); } } void Get_round(int x,int y,int c,int round[6]) { f[x][y]=1; for(int i=0;i<4;i++) { int nx=x+xx[i]; int ny=y+yy[i]; if(nx>0&&nx<=n&&ny>0&&ny<=n&&f[nx][ny]==0) { if(a[nx][ny]==c)Get_round(nx,ny,c,round); else if(round[a[nx][ny]]==0)round[a[nx][ny]]=1; } } } void Dfs(int now,int sum) { if(falg)return; memset(vis,0,sizeof(vis));C=0; for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(vis[a[i][j]]==0){vis[a[i][j]]=1;C++;} if(now==sum) { if(C==1)falg=1; return; } if(now+C-1>sum)return; memset(f,0,sizeof(f)); int round[6];memset(round,0,sizeof(round)); Get_round(1,1,a[1][1],round); for(int i=0;i<=5;i++) { if(i==a[1][1]||round[i]==0)continue; int back[9][9]; memcpy(back,a,sizeof(a)); memset(f,0,sizeof(f)); Go(1,1,a[1][1],i); Dfs(now+1,sum);if(falg)return; memcpy(a,back,sizeof(back)); } } int main() { while(1) { n=init();if(n==0)break; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) g[i][j]=init(); for(int k=0;k<=16;k++) { memcpy(a,g,sizeof(g)); falg=0;Dfs(0,k); if(falg) { ans=k;break; } } printf("%d ",ans); } return 0; }
/* 只像上面那样好像A不了 （也可能是我常数太大了QAQ...） 最后没办法了 看了题解 每次灌水的时候似乎很慢 我们处理f数组 1表示已经在左上角 2表示在左上角的周围 这样不灌水 同样的处理了这个问题 虽然过了 但还是跑的比较慢..... */ #include<iostream> #include<cstdio> #include<cstring> using namespace std; int n,ans,g[9][9],tot,color,falg,f[9][9],vis[6],C; int xx[4]={0,0,-1,1}; int yy[4]={1,-1,0,0}; int init() { int x=0;char s=getchar(); while(s<'0'||s>'9')s=getchar(); while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} return x; } void dfs(int x,int y,int r) { f[x][y]=1; for(int i=0;i<4;i++) { int nx=x+xx[i]; int ny=y+yy[i]; if(nx>0&&nx<=n&&ny>0&&ny<=n&&f[nx][ny]==0) { if(g[nx][ny]==r)dfs(nx,ny,r); else f[nx][ny]=2; } } } bool Go(int r) { int ret=0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(f[i][j]==2&&g[i][j]==r) ret=1,dfs(i,j,r); return ret; } void Dfs(int now,int sum) { if(falg)return; memset(vis,0,sizeof(vis));C=0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(vis[g[i][j]]==0&&f[i][j]!=1) vis[g[i][j]]=1,C++; if(now==sum) { if(C==0)falg=1; return; } if(now+C-1>sum)return; int back[9][9]; memcpy(back,f,sizeof(f)); for(int i=0;i<=5;i++) { if(Go(i))Dfs(now+1,sum); if(falg)return; memcpy(f,back,sizeof(back)); } } int main() { while(1) { n=init();if(n==0)break; memset(f,0,sizeof(f)); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) g[i][j]=init(); dfs(1,1,g[1][1]); for(int k=0;k<=16;k++) { falg=0;Dfs(0,k); if(falg){ans=k;break;} } printf("%d ",ans); } return 0; }