首页 > 代码库 > [CodeVS]2495:水叮当的舞步

[CodeVS]2495:水叮当的舞步

传送门

A*搜索练习,以还剩余多少种颜色为估价,写的时候把2打成了1查了一个多小时。

 

//codevs 2495//by Cydiater//2016.10.11#include <iostream>#include <cstring>#include <cstdlib>#include <cstdio>#include <queue>#include <map>#include <ctime>#include <cstdlib>#include <cmath>#include <iomanip>#include <algorithm>using namespace std;#define ll long long#define up(i,j,n)		for(int i=j;i<=n;i++)#define down(i,j,n)		for(int i=j;i>=n;i--)#define pii pair<int,int>#define mp make_pairconst int MAXN=9;const int oo=0x3f3f3f3f;const int dx[4]={1,0,-1,0};const int dy[4]={0,1,0,-1};inline int read(){	char ch=getchar();int x=0,f=1;	while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}	while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}	return x*f;}int N,color[MAXN][MAXN],rec[MAXN][MAXN],tmp[MAXN][MAXN],cnt[10];bool OK,vis[MAXN][MAXN];namespace solution{	void init(){		scanf("%d\n",&N);if(N==0)exit(0);		memset(rec,0,sizeof(rec));		up(i,1,N)up(j,1,N)color[i][j]=read();	}	void dfs(int x,int y,int col){		rec[x][y]=1;		up(i,0,3){			int tx=x+dx[i],ty=y+dy[i];			if(tx>N||tx<1||ty>N||ty<1||rec[tx][ty]==1)continue;			if(color[tx][ty]==col)	dfs(tx,ty,col);			else 					rec[tx][ty]=2;		}	}	int get(){		int ans=0;		memset(cnt,0,sizeof(cnt));		up(i,1,N)up(j,1,N)if(rec[i][j]!=1&&!cnt[color[i][j]]){				ans++;cnt[color[i][j]]=1;		}		return ans;	}	bool fill(int col){		bool flag=0;		up(i,1,N)up(j,1,N)if(rec[i][j]==2&&color[i][j]==col){			flag=1;			dfs(i,j,color[i][j]);		}		return flag;	}	void search(int dep,int depth,int now){		if(OK)return;		int v=get();		if(v==0){			OK=1;			return;		}		if(dep+v>depth)return;		int ttt[MAXN][MAXN];		up(i,0,5){			memcpy(ttt,rec,sizeof(rec));			if(fill(i))search(dep+1,depth,i);			memcpy(rec,ttt,sizeof(ttt));		}	}	void slove(){		dfs(1,1,color[1][1]);		OK=0;		up(dep,0,20){			search(0,dep,color[1][1]);			if(OK){				printf("%d\n",dep);				return;			}		}	}}int main(){	using namespace solution;	while(1){		init();		slove();	}	return 0;}

[CodeVS]2495:水叮当的舞步