UVA1505 Flood-it! 题解

· · 题解

题目链接

此题算法 IDA*

IDA* 是指带有预估函数的迭代加深算法，相比 A-Star 算法，其优势在于节省了优先队列的 O(\log n) 的复杂度，同时节省了空间 (A-Star 算法需要用到队列）。

IDA* 算法要点：

1 . 控制迭代加深深度。若题目说在 x 步内无法求得答案，则 x 为最大限制深度。

2 . 设计合理的预估函数。预估函数越大，优化越多。但预估函数不可以大于未来实际代价，这是设计预估函数的基本原则。特别的，当预估函数为 0 时，搜索就是爆搜。

分析

首先，由于 N 很小，所以自然想到搜索或者状态压缩。此题选择搜索 (IDA*)。

既然是 IDA* ， 那我们先来求预估函数。显然，本题的预估函数 f() 为还没有走到过的点有多少种颜色，考虑每次开一个桶来求。复杂度:O(n^2)<=64 。

另外，该题不同于 IDA* 模板题的地方就是要扩展一下颜色，代码中详见。代码中的 vis_{i,j} =1 时表示该点已经访问过了，vis_{i,j}=2 时表示在访问区的边缘（自行理解），vis_{i,j}=0 时该点还没有用到。

另外，还有 expand 函数和 change 函数的区别在于 expand 是维护（扩展）连通块的，而另一个是初步改变

最后，就是套路的迭代加深了。

代码

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
int n,map[10][10];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int vis[10][10];
int f(){  //预估函数
    int cnt=0;
    int t[10]={false}; //桶
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
        if(!t[map[i][j]]&&vis[i][j]!=1){ //在还没有走到的点中求颜色有多少种
          cnt++;
          t[map[i][j]]=true;
        }
    return cnt; 
}
bool valid(int x,int y){
    return x>=1&&x<=n&&y>=1&&y<=n&&vis[x][y]!=1;
}
void expand(int x,int y,int cor){
    vis[x][y]=1;  //已访问
    for(int i=0;i<4;i++){
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(!valid(xx,yy)) continue;
        vis[xx][yy]=2; //在访问的边缘
        if(map[xx][yy]==cor) expand(xx,yy,cor); //若颜色相同，就还可以扩展
    }
}
int change(int cor){
    int res=0;
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
        if(vis[i][j]==2&&map[i][j]==cor){ //在扩展边缘上并且颜色与新选的一致
          expand(i,j,cor); res++;
        }
    return res;
}
bool dfs(int dep,int maxdep){
    if(dep+f()>maxdep) return false;
    if(!f()) return true;
    int t[10][10]; //小数组可以开到局部
    for(int i=0;i<=5;i++){
        memcpy(t,vis,sizeof vis);
        if(change(i)&&dfs(dep+1,maxdep)) return true;  //change(i)==true 表示此次颜色扩展有效（也就是有新的格子换了颜色）
        memcpy(vis,t,sizeof vis); //还原现场
    }
    return false;
}
int main(){
    while(scanf("%d",&n)&&n){
        memset(vis,0,sizeof vis); //清空不要忘了
        for(int i=1;i<=n;i++)
          for(int j=1;j<=n;j++)
            scanf("%d",&map[i][j]);
        int maxdep=0;
        expand(1,1,map[1][1]); //首先处理处左上角同样颜色的点集
        while(!dfs(0,maxdep)) maxdep++; //迭代加深
        printf("%d\n",maxdep);
    }
    return 0;
}