题目描述

Description

水叮当得到了一块五颜六色的格子形地毯作为生日礼物，更加特别的是，地毯上格子的颜色还能随着踩踏而改变。
为了讨好她的偶像虹猫，水叮当决定在地毯上跳一支轻盈的舞来卖萌~~~
地毯上的格子有N行N列，每个格子用一个0~5之间的数字代表它的颜色。
水叮当可以随意选择一个0~5之间的颜色，然后轻轻地跳动一步，左上角的格子所在的联通块里的所有格子就会变成她选择的那种颜色。这里连通定义为：两个格子有公共边，并且颜色相同。
由于水叮当是施展轻功来跳舞的，为了不消耗过多的真气，她想知道最少要多少步才能把所有格子的颜色变成一样的。

Input

每个测试点包含多组数据。
每组数据的第一行是一个整数N，表示地摊上的格子有N行N列。
接下来一个N*N的矩阵，矩阵中的每个数都在0~5之间，描述了每个格子的颜色。
N=0代表输入的结束。

Output

对于每组数据，输出一个整数，表示最少步数。

Sample Input

2
0 0 
0 0
3
0 1 2
1 1 2
2 2 1
0

Sample Output

0
3

HINT

对于100%的数据，N<=8，每个测试点不多于20组数据。

题目分析：

迭代加深搜索+A*(剪枝)
因为dfs只能存局部 一开始在dfs函数里传了二维数组形参 尽管代码超好写直接MLE= =
于是看了hzwer的题解 好强啊
就是设立vis数组 将左上角所在的联通块内标为1 边界标为2 其余不用管
这样的话直接根据a数组在vis数组上更改 就不用改a数组了

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n;
int a[9][9],v[9][9];
int now;
int dx[5]={0,0,1,-1};
int dy[5]={1,-1,0,0};
void color(int x,int y,int c)
{
    v[x][y]=1;
    for(int i=0;i<4;i++)
    {
        int dxx=dx[i]+x,dyy=dy[i]+y;
        if(dxx>n||dyy>n||dyy<1||dxx<1||v[dxx][dyy]==1) continue;
        v[dxx][dyy]=2;
        if(a[dxx][dyy]==c) color(dxx,dyy,c);
    }
    return ;
}
bool vis[6];
int check()
{
    for(int i=0;i<=5;i++) vis[i]=0; 
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(v[i][j]!=1) vis[a[i][j]]=1;
    int cnt=0;
    for(int i=0;i<=5;i++) if(vis[i]) cnt++;
    return cnt;
}
int judge(int val)
{
    int flag=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(v[i][j]==2&&a[i][j]==val)
            {
                color(i,j,val);
                flag=1;
            }
    return flag;
}
int dfs(int deep)
{
    int p=check();
    if(!p) return 1;
    if(p+deep>now) return 0;
    int tmp[9][9];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++) tmp[i][j]=v[i][j];
    for(int i=0;i<=5;i++)
    {
        if(judge(i)&&dfs(deep+1)) return 1;
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++) v[j][k]=tmp[j][k];
    }   
    return 0;
}   
int main()
{
    while(scanf("%d",&n) && n)
    {
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                scanf("%d",&a[i][j]);
        memset(v,0,sizeof v);
        color(1,1,a[1][1]);
        for(now=0;now<=n*n;now++)
            if(dfs(0)) 
            {
                printf("%d\n",now);
                break;
            }
    }
    return 0;
}