【codevs2495】 水叮当的舞步

时间：2023-03-08 17:10:21

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;

}

　　

相关文章