/*比较简单的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\n",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\n",ans);      }    return 0;}