首页 > 代码库 > [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:水叮当的舞步
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。