Trial for Chief

wjh15101051's space

卧薪尝胆，厚积薄发。

Trial for Chief

Date: Fri Jul 06 22:00:52 CST 2018

In Category: NoCategory

Description：

要把一块大小为 $N\times M$ 的白木板的某些格子涂成黑色。每次可以选择一个连通块，全涂白或者全涂黑，问最少要涂几次。

$N,M\le50$

Solution：

每个点和他周围四个点连边，颜色相同权值为 $0$ ，不同权值为 $1$ ，枚举每个点，求出它到最远的黑点的距离，取 $min+1$ 即为答案。

举个例子：

$WB\ W$

$B\ WB\ $

$WB\ W$

如果以左上角为起点，则答案为：

0 1 2

1 2 3

2 3 4

代表先将右下角染完，再阶梯向上染。最后染到左上角。

如果以中间为起点，则结果为：

2 1 2

1 0 1

2 1 2

结果为 $3$ 。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 51

char map[MAXN][MAXN];

char getc()

{

	char c = getchar();

	while(c != 'W' && c != 'B')c = getchar();

	return c;

}

int to(int x,int y){return (x - 1) * m + y;}

struct edge

{

	int to,nxt,v;

}e[MAXN * MAXN * 4 * 2];

int edgenum = 0;

int lin[MAXN * MAXN] = {0};

void add(int a,int b,int c)

{

	++edgenum;e[edgenum].to = b;e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	return;

}

int d[MAXN * MAXN];

bool v[MAXN * MAXN];

void SPFA(int s)

{

	memset(d,0x3f,sizeof(d));

	memset(v,0,sizeof(v));

	queue<int> q;

	q.push(s);

	d[s] = 0;

	v[s] = true;

	while(!q.empty())

	{

		int k = q.front();q.pop();

		v[k] = false;

		for(int i = lin[k];i != 0;i = e[i].nxt)

		{

			if(d[e[i].to] > d[k] + e[i].v)

			{

				d[e[i].to] = d[k] + e[i].v;

				if(!v[e[i].to])

				{

					v[e[i].to] = true;

					q.push(e[i].to);

				}

			}

		}

	}

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= m;++j)

		{

			map[i][j] = getc();

		}

	}

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= m;++j)

		{

			if(i > 1)add(to(i,j),to(i - 1,j),(map[i][j] != map[i - 1][j] ? 1 : 0));

			if(i < n)add(to(i,j),to(i + 1,j),(map[i][j] != map[i + 1][j] ? 1 : 0));

			if(j > 1)add(to(i,j),to(i,j - 1),(map[i][j] != map[i][j - 1] ? 1 : 0));

			if(j < m)add(to(i,j),to(i,j + 1),(map[i][j] != map[i][j + 1] ? 1 : 0));

		}

	}

	int ans = 0x3f3f3f3f;

	bool found = false;

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= m;++j)

		{

			int res = 0;

			if(map[i][j] == 'B')found = true;

			SPFA(to(i,j));

			for(int i0 = 1;i0 <= n;++i0)

			{

				for(int j0 = 1;j0 <= m;++j0)

				{

					if(map[i0][j0] == 'B')

					{

						res = max(res,d[to(i0,j0)]);

					}

				}

			}

			ans = min(ans,res);

		}

	}

	if(found)cout << ans + 1 << endl;

	else puts("0");

	return 0;

}

In tag: 图论-SPFA

wjh15101051