UVA1505 Flood-it!

题意

给出一个 $N\times N$ 的矩形，每个格子染有 $0..5$ 这 $6$ 种颜色。每次操作可以把左上角格子所在的同色联通块全部染成一种颜色，求把所有格子染成一种颜色至少需要多少种操作？

$N\le 8$ 。多组数据，组数 $T\le 20$ 。

题解

朴素的搜索为每次枚举要染的颜色，染色后继续搜索直到染完。退出的条件为某次染色没有新增的格子。期望得分30。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int n,ans,s[10][10];
const int fx[4]={0,0,1,-1},fy[4]={1,-1,0,0};

void work(int x,int y,int c,int &cnt,int col)
{
    cnt++;
    s[x][y]=c;
    for (int i=0;i<4;i++)
    {
        int tx=x+fx[i],ty=y+fy[i];
        if (tx<1 || tx>n || ty<1 || ty>n) continue;
        if (s[tx][ty]!=col) continue;
        work(tx,ty,c,cnt,col);
    }
}

inline bool check()
{
    for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (s[i][j]!=s[1][1]) return 0;
    return 1;
}

void dfs(int col,int cur,int last)
{
    if (col==s[1][1]) return;
    if (cur>=ans) return;
    if (check()) return (void)(ans=cur);
    bool vis2[10][10]; int s2[10][10];
    memcpy(s2,s,sizeof(s));
    int cnt=0;
    work(1,1,col,cnt,s[1][1]);
    if (cnt<=last) goto back;
    for (int i=0;i<6;i++) if (i!=col) dfs(i,cur+1,cnt);
    back:
    memcpy(s,s2,sizeof(s));
}

signed main()
{
    while (~scanf("%d",&n) && n)
    {
        ans=1e9;
        for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) s[i][j]=read();
        for (int i=0;i<6;i++) dfs(i,0,0);
        printf("%d\n",ans);
    }
    return 0;
}

显然每次从 $(1,1)$ 开始重新染色的时间开销过大，考虑只维护新增的格子。

对所有格子在 $(1,1)$ 所在联通块的情况，使用新标记 $col[x]$ 记录。如果在则 $col[x]=1$ ；如果在联通块的边缘，即下一步就染的 $col[x]=2$ ；否则 $col[x]=0$ 。每次染色枚举 $col[x]=2$ 的格子即可。

还需要使用迭代加深优化。剪枝就是当前深度 $+$ 不在联通块的格子的颜色数 $>$ 最大深度则退出。显然剩下的格子有多少种颜色就至少要做几次。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int n,ans,s[10][10],col[10][10];
const int fx[4]={0,0,1,-1},fy[4]={1,-1,0,0};

inline void work(int,int,int);
inline bool check(int);
inline int left();
bool dfs(int);

signed main()
{
    while (~scanf("%d",&n) && n)
    {
        memset(col,0,sizeof(col));
        for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) s[i][j]=read();
        work(1,1,s[1][1]); //先对 (1,1) 染色
        for (ans=0;;ans++) if (dfs(0)) {printf("%d\n",ans); break; }
    }
    return 0;
}

bool dfs(int dep) //主过程
{
    int l=left();
    if (!l) return 1;
    if (dep+l>ans) return 0;
    int col2[10][10];
    for (int i=0;i<6;i++)
    {
        memcpy(col2,col,sizeof(col));
        if (check(i) && dfs(dep+1)) return 1;
        memcpy(col,col2,sizeof(col));
    }
    return 0;
}

inline int left() //剩余的颜色数
{
    bool ccnt[6]; memset(ccnt,0,sizeof(ccnt));
    int res=0;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            if (col[i][j]==1 || ccnt[s[i][j]]) continue;
            ccnt[s[i][j]]=1;
            res++;
        }
    }
    return res;
}

inline bool check(int x) //检查某种颜色是否能染
{
    bool res=0;
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            if (col[i][j]!=2 || s[i][j]!=x) continue;
            work(i,j,x);
            res=1;
        }
    }
    return res;
}

inline void work(int x,int y,int c) //染色
{
    col[x][y]=1;
    for (int i=0;i<4;i++)
    {
        int tx=x+fx[i],ty=y+fy[i];
        if (tx<1 || tx>n || ty<1 || ty>n || col[tx][ty]==1) continue;
        col[tx][ty]=2;
        if (s[tx][ty]==c) work(tx,ty,c);
    }
}