首页 > 代码库 > 【codevs2495】 水叮当的舞步
【codevs2495】 水叮当的舞步
http://codevs.cn/problem/2495/ (题目链接)
题意
给出一个N*N的矩阵，其中元素有5种颜色，每次可以将左上角元素所在的连通块更换一种颜色，连通块指相邻并且颜色相同的元素在同一连通块内。问最少改变几次颜色使得所有元素颜色相同。
Solution
刚开始打了个迭代加深，get了20分。。。考虑如何对它进行优化。
一个很显然的优化就是染色的时候，只对连通块周围的属于连通块的一圈元素进行扩展，并保存下染色后新的外圈元素。
可是仅仅这样还是不够,只能get50分。
考虑A*，如何构造估价函数呢。显然，如果剩下的不属于连通块的元素有cnt种不同的颜色，那么至少还需要染色cnt次，那么如果cnt+当前步数>枚举深度d，显然这样走下去不会出答案，直接退出即可。
细节
细节有点恶心，刚开始我用的bfs实现染色操作，然后回溯还有各种不好做的操作，就直接翻了题解。。真是很优美。。
代码
// codevs2495#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#include<queue>#define LL long long#define inf 2147483640#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;int xx[4]={0,0,-1,1};int yy[4]={1,-1,0,0};int a[10][10],vis[10][10],e[6];int n,flag,d;void color(int x,int y,int col) { vis[x][y]=1; for (int i=0;i<4;i++) { int nx=x+xx[i],ny=y+yy[i]; if (nx<1 || nx>n || ny<1 || ny>n || vis[nx][ny]==1) continue; vis[nx][ny]=2; if (a[nx][ny]==col) color(nx,ny,col); }}int eva(int s) { int cnt=0; memset(e,0,sizeof(e)); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (vis[i][j]!=1 && !e[a[i][j]]) e[a[i][j]]=1,cnt++; return cnt;}bool judge(int col) { int tmp=0; for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (a[i][j]==col && vis[i][j]==2) { tmp++; color(i,j,col); } return tmp>0;}void search(int s) { int tmp=eva(s),t[10][10]; if (tmp==0) {flag=1;return;} else if (tmp+s>d) return; for (int i=0;i<=5;i++) { memcpy(t,vis,sizeof(t)); if (judge(i)) search(s+1); memcpy(vis,t,sizeof(vis)); if (flag) return; }}int main() { while (scanf("%d",&n)!=EOF && n) { flag=0;memset(vis,0,sizeof(vis)); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) scanf("%d",&a[i][j]); color(1,1,a[1][1]); for (d=0;d>=0;d++) { search(0); if (flag) {printf("%d\n",d);break;} } } return 0;}
【codevs2495】 水叮当的舞步
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。