POJ4007 Flood-it! 题解

调得我快死了啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊！！！！

先自己写了几发，老是 T，然后去看题解，大体思路居然都差不多，估计是自己写挂了orz。

几乎所有题解都有个vis数组，真 nm 看不懂到底是什么意思啊啊啊！！！

然后照着题解打了一遍后好像明白了……emmm……

vis为 1 时代表当前位置与 (0,0) 颜色相同并且联通，等于 2 时代表与 (0,0) 颜色不同但修改颜色时可能会变得联通（即和值为一的位置相邻）。

每次选择一个当前值等于 2 的位置（即这个位置可扩展连通块），以它为中心求一下vis数组，这样很巧妙地避免了从 (0,0) 重新染色。

这么妙啊……这个vis数组还真没想到……

#include <bits/stdc++.h>

using namespace std;

const int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};

int n,a[8][8],cpy[50][8][8],vis[8][8];

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

{

	vis[x][y]=1;

	for(int i=0;i<4;++i)

	{

		int nx=x+dx[i],ny=y+dy[i];

		if(nx<0||ny<0||nx>=n||ny>=n) continue;

		if(vis[nx][ny]==1) continue;

		vis[nx][ny]=2;

		if(a[nx][ny]==c) paint(nx,ny,c);

	}

}

int f()

{

	int ans=0;

	static bool cnt[6];

	memset(cnt,0,sizeof(cnt));

	for(int i=0;i<n;++i)

		for(int j=0;j<n;++j)

		 	if(!cnt[a[i][j]]&&vis[i][j]!=1)

		 		cnt[a[i][j]]=1,++ans;

	return ans;

}

bool dfs(int dep,int max_dep)

{

	int t=f();

	if(dep+t>max_dep) return 0;

	if(!t) return 1;

	memcpy(cpy[dep],vis,sizeof(vis));

	for(int i=0;i<6;++i)

	{

		bool fl=0;

		for(int x=0;x<n;++x)

			for(int y=0;y<n;++y)

				if(a[x][y]==i&&vis[x][y]==2)

				{

				    fl=1;paint(x,y,i);

				}

		if(fl&&dfs(dep+1,max_dep)) return 1;

		memcpy(vis,cpy[dep],sizeof(vis));

	}

	return 0;

}

int main()

{

	while(scanf("%d",&n)&&n)

	{

		for(int i=0;i<n;++i)

			for(int j=0;j<n;++j)

				scanf("%d",&a[i][j]);

		memset(vis,0,sizeof(vis));

		paint(0,0,a[0][0]);

		int dep=0;

		while(!dfs(0,dep)) ++dep;

		printf("%d\n",dep);

	}

	return 0;

}

巴特西

POJ4007 Flood-it! 题解

最新文章

热门文章