ID(dfs+bfs)-hdu-4127-Flood-it!

题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=4127

题目意思:

给n*n的方格,每个格子有一种颜色(0~5),每次可以选择一种颜色,使得和左上角相连(颜色相同以及相邻,间接也行)的所有的格子都为该颜色。求最少的步数,使得所有的方格颜色都相同。

解题思路:

bfs+bfs死活不给过。

正确解法应该是ID(dfs+bfs).因为总共的解的步数不多。

减枝:

1、当剩余的颜色种数(至少还要这么多步)+已走的步数>设定深度时 跳出。

2、注意每次搜的时候保证比前面的方格数多。

PS:时间卡的紧,不用STL,用手写队列。

代码:

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std; #define Maxn 10
int sa[Maxn][Maxn],n,ans,dep;
int dir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};
bool flag; struct Po
{
int x,y;
}q[80]; struct Inf
{
int cnt;
Po pp[70];
}; //存储一个连通块内的所有节点
bool vis[Maxn][Maxn];
bool iscan(int x,int y) //判断是否越界
{
if(x<=0||x>n||y<=0||y>n)
return false;
return true;
}
void bfs(Inf & s,int co[])
{
memset(vis,false,sizeof(vis));
//queue<Inf>myq;
s.cnt=0;
Po tmp;
tmp.x=1,tmp.y=1;
s.pp[++s.cnt]=tmp;
vis[1][1]=true;
//myq.push(s);
int head=0,tail=-1;
q[++tail]=tmp; while(head<=tail)
{
//Inf cur=myq.front();
//myq.pop();
Po cur=q[head];
++head; int xx=cur.x,yy=cur.y;
for(int i=0;i<4;i++)
{
int x=xx+dir[i][0],y=yy+dir[i][1];
if(!iscan(x,y)||vis[x][y]||sa[x][y]!=sa[xx][yy])
continue;
vis[x][y]=true;
Po tt;
tt.x=x,tt.y=y;
s.pp[++s.cnt]=tt;
//myq.push(s);
q[++tail]=tt;
}
}
for(int i=1;i<=n;i++) //统计还没有进入连通块内的颜色种数
for(int j=1;j<=n;j++)
{
if(!vis[i][j])
co[sa[i][j]]++;
} }
void dfs(int co,int step,int num) //当前颜色,已走步数,已联通的方格个数
{
if(step>dep||flag)
return ;
int cc[6]={0};
Inf tmp;
bfs(tmp,cc);
if(tmp.cnt<=num)//往多的方格搜,不然浪费步数
return ;
num=tmp.cnt;
//printf(":%d\n",num);
//system("pause");
if(num==n*n) //找到了
{
flag=true;
ans=step;
return ;
}
int nn=0;
for(int i=0;i<6;i++)
if(cc[i])
nn++;
if(nn+step>dep) //至少要这么多步
return ;
for(int i=0;i<6;i++)
{
if(i==co)
continue;
for(int j=1;j<=tmp.cnt;j++)
sa[tmp.pp[j].x][tmp.pp[j].y]=i;
dfs(i,step+1,num);
for(int j=1;j<=tmp.cnt;j++) //回溯
sa[tmp.pp[j].x][tmp.pp[j].y]=co;
} }
void IDA()
{
flag=false;
dep=1;
while(!flag) //迭代加深搜索
{
dfs(sa[1][1],0,0);
++dep;
}
} int main()
{
while(scanf("%d",&n)&&n)
{
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&sa[i][j]);
IDA();
printf("%d\n",ans);
}
return 0;
}
上一篇:Web大文件(夹)上传(断点续传)控件-Xproer.HttpUploader6


下一篇:VMware安装Centos7,已将该虚拟机配置为使用64为,却无法执行64位操作