当前位置:编程学习 > C/C++ >>

HDU 4127 Flood-it!(11年福州 IDA*搜索)

一个游戏,n*n的方格,每次将左上角的染色,相应的一个连通块全部染色,连通块的定义为,4个方向相邻的,而且颜色一样的。

 

问最少的步数,IDA*搜索。

重要的一步是将整个方格分为3个部分,第一部分是和左上角在一个连通块的,标为1,第二部分为和连通块颜色不一样,但是相邻的,标为2,可以知道,标为2的部分是我们染色的选择,将连通块染成2的颜色,那样就将这个方块加入到连通块中。

A*剪枝,剩下的中还有多少种颜色,说明至少要染色多少次。


[cpp]
#include<iostream>  
#include<cstdio>  
#include<map>  
#include<cstring>  
#include<cmath>  
#include<vector>  
#include<algorithm>  
#include<set>  
#include<string>  
#include<queue>  
#define inf 1<<30  
#define M 60005  
#define N 10005  
#define maxn 300005  
#define eps 1e-10  
#define zero(a) fabs(a)<eps  
#define Min(a,b) ((a)<(b)?(a):(b))  
#define Max(a,b) ((a)>(b)?(a):(b))  
#define pb(a) push_back(a)  
#define mem(a,b) memset(a,b,sizeof(a))  
#define LL long long  
#define lson step<<1  
#define rson step<<1|1  
#define MOD 1000000009  
using namespace std; 
int maze[10][10]; 
int n; 
int way[4][2]={0,1,0,-1,1,0,-1,0}; 
int vis[10][10];//给每个节点一个编号,如果是1表示和左上连通,如果为2表示不和左上直接连通,但是和左上连通块相邻  
bool check(int x,int y) 

    if(x<0||y<0||x>=n||y>=n) return false; 
    return true; 

void floodfill(int x,int y,int c) 

    vis[x][y]=1; 
    for(int i=0;i<4;i++) 
    { 
        int tx=x+way[i][0]; 
        int ty=y+way[i][1]; 
        if(!check(tx,ty)) continue; 
        if(vis[tx][ty]==1) continue; 
        if(maze[tx][ty]==c) floodfill(tx,ty,c); 
        else vis[tx][ty]=2; 
    } 

//如果染col的话,有多少个格子会加入连通块中  
int get_cnt(int col) 

    int cnt=0; 
    for(int i=0;i<n;i++) 
    { 
        for(int j=0;j<n;j++) 
        { 
            if(maze[i][j]==col&&vis[i][j]==2) 
            { 
                cnt++; 
                floodfill(i,j,maze[i][j]); 
            } 
        } 
    } 
    return cnt; 

//估价函数,表示除了连通块的部分,有多少种颜色  
//也就是至少需要染色多少次  
int get_h() 

    bool flag[6];mem(flag,false); 
    int cnt=0; 
    for(int i=0;i<n;i++) 
    { 
        for(int j=0;j<n;j++) 
        { 
            if(vis[i][j]!=1&&!flag[maze[i][j]]) 
            { 
                cnt++; 
                flag[maze[i][j]]=true; 
            } 
        } 
    } 
    return cnt; 

int depth; 
bool IDAstar(int dep) 

    if(depth==dep) return get_h()==0; 
    if(dep+get_h()>depth) return false; 
    for(int i=0;i<6;i++) 
    { 
        int tmp[10][10]; 
        memcpy(tmp,vis,sizeof(vis)); 
        //染色没有效果  
        if(get_cnt(i)==0) continue; 
        if(IDAstar(dep+1)) return true; 
        memcpy(vis,tmp,sizeof(vis)); 
    } 
    return false; 

int main() 

    while(scanf("%d",&n)!=EOF&&n) 
    { 
        for(int i=0;i<n;i++) 
        { 
            for(int j=0;j<n;j++) 
            { 
                scanf("%d",&maze[i][j]); 
            } 
        } 
        mem(vis,0); 
        floodfill(0,0,maze[0][0]); 
        depth=get_h(); 
        while(true) 
        { 
            if(IDAstar(0)) break; 
            depth++; 
        } 
        printf("%d\n",depth); 
    } 
    return 0; 

#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<queue>
#define inf 1<<30
#define M 60005
#define N 10005
#define maxn 300005
#define eps 1e-10
#define zero(a) fabs(a)<eps
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define pb(a) push_back(a)
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define lson step<<1
#define rson step<<1|1
#define MOD 1000000009
us

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,