首页 > 代码库 > 【wikioi】2495 水叮当的舞步（A*+迭代加深搜索）

【wikioi】2495 水叮当的舞步（A*+迭代加深搜索）

2024-07-16 05:03:52   217人阅读

 

这题我还是看题解啊囧。（搜索实在太弱。完全没想到A*，还有看题的时候想错了，。，- -）

好吧，估价还是那么的简单，判断颜色不同的数目即可（左上角的联通块不算在内）

然后A*还是一样的做法。

迭代加深还是一样的味道～

在这里我们用c[i][j]来表示左上角开始的联通块和联通块外面一层（因为要从外面一层拓展颜色），分别记为1和2

那么我们在搜索的时候，染色只要染c[i][j]为2的颜色种类，并且更新联通块（在这里不需要传图，因为一层一层的拓展下去的话，是单调递增的，所以用不到之前的颜色）我们在搜索前只需要维护之前的c数组然后更新完后再还原回来即可。

#include <cstdio>#include <cstring>#include <cmath>#include <string>#include <iostream>#include <algorithm>using namespace std;#define rep(i, n) for(int i=0; i<(n); ++i)#define for1(i,a,n) for(int i=(a);i<=(n);++i)#define for2(i,a,n) for(int i=(a);i<(n);++i)#define for3(i,a,n) for(int i=(a);i>=(n);--i)#define for4(i,a,n) for(int i=(a);i>(n);--i)#define CC(i,a) memset(i,a,sizeof(i))#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))#define read(a) a=getnum()#define print(a) printf("%d", a)inline int getnum() { int ret=0; char c; int k=1; for(c=getchar(); c<‘0‘ || c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘ && c<=‘9‘; c=getchar()) ret=ret*10+c-‘0‘; return k*ret; }const int N=8;int m[N][N], c[N][N], n, ans;int fx[4]={-1, 1, 0, 0}, fy[4]={0, 0, -1, 1};bool used[6];inline int H() {	int ret=0;	CC(used, 0);	rep(i, n) rep(j, n)		if(!used[m[i][j]] && c[i][j]!=1)			used[m[i][j]]=true, ++ret;	return ret;}void change2(const int &x, const int &y, const int &color) {	c[x][y]=1;	int nx, ny;	rep(i, 4) {		nx=x+fx[i], ny=y+fy[i];		if(nx<0 || nx>=n || ny<0 || ny>=n || c[nx][ny]==1) continue;		c[nx][ny]=2;		if(m[nx][ny]==color) change2(nx, ny, color);	}}inline bool change(const int &color) {	bool ret=false;	rep(i, n) rep(j, n) if(c[i][j]==2 && m[i][j]==color) ret=true, change2(i, j, color);	return ret;}bool dfs(const int &g) {	int h=H();	if(g+h>ans) return false;	if(!h) return true;	int t[N][N];	memcpy(t, c, sizeof(c));	for1(i, 0, 5) {		if(change(i) && dfs(g+1)) return true;		memcpy(c, t, sizeof(t));	}	return false;}int main() {	for(read(n); n; read(n)) {		CC(c, 0); CC(m, 0);		rep(i, n) rep(j, n) read(m[i][j]);		change2(0, 0, m[0][0]);		for(ans=0; ; ++ans)			if(dfs(0)) break;		printf("%d\n", ans);	}		return 0;}

 


联系
我们