#297 (div.2) D. Arthur and Walls

1.题目描述：点击打开链接

2.解题思路：本题利用BFS解决。一开始想用dfs去搜索连通块，再想办法找到该连通块的左上角和最大的长，宽，然后把该区域都变成‘.‘，显然这种做法无法处理规模较大的情况。此时应该从分治的思想去考虑。找到一个最基本的元素块，把长方体看做是由这些元素块构造出来的即可。那么这种元素块应该是什么样的呢？

通过观察不难发现，所有需要变为‘.‘的点周围肯定都是‘.‘。换句话说，在(i,j)处是‘*’,周围是‘.‘的2*2的方块可以看做一个元素块。先通过扫描找到所有的元素块，然后利用BFS向外扩展，每次出队列时，把(i,j)处修改为‘.‘即可。这样经过一次BFS，即可实现连通块都是长方形。注意：每次出队列后都要再次检查是否仍为元素块，因为该元素块的‘*‘可能会被中途修改！如果没有此处判断，会导致TLE！

3.代码：

#define _CRT_SECURE_NO_WARNINGS 
#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>
#include<set>
#include<vector>
#include<stack>
#include<map>
#include<queue>
#include<deque>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<ctime>
#include<functional>
using namespace std;

typedef pair<int, int> P;
#define N 2005
int n, m;
char g[N][N];

bool check(int x, int y)//找到元素块
{
	if (g[x][y] == '.' || x < 0 || y < 0 || x >= n || y >= m)return 0;
	if (g[x][y - 1] == '.'&&g[x - 1][y - 1] == '.'&&g[x - 1][y] == '.')return 1;
	if (g[x - 1][y] == '.'&&g[x - 1][y + 1] == '.'&&g[x][y + 1] == '.')return 1;
	if (g[x][y + 1] == '.'&&g[x + 1][y + 1] == '.'&&g[x + 1][y] == '.')return 1;
	if (g[x][y - 1] == '.'&&g[x + 1][y - 1] == '.'&&g[x + 1][y] == '.')return 1;
	return 0;
}

int main()
{
	//freopen("t.txt", "r", stdin);
	while (~scanf("%d%d", &n, &m))
	{
		for (int i = 0; i < n; i++)
			scanf("%s", g[i]);
		queue<P>q;
		for (int i = 0; i < n;i++)
		for (int j = 0; j < m;j++)
		if (check(i, j))
			q.push(P(i, j));
		while (!q.empty())
		{
			P u = q.front(); q.pop();
			int i = u.first, j = u.second;
			if (!check(i, j))continue;//必须有此处判断!因为g[i][j]=='*'可能在出队列之前就被修改为'.'了
			g[i][j] = '.';
			for (int x = -2; x <= 2;x++)
			for (int y = -2; y <= 2; y++)
			if ((x || y) && check(i + x, j + y))
				q.push(P(i + x, j + y));
		}
		for (int i = 0; i < n; i++)
			puts(g[i]);
	}
	return 0;
}

#297 (div.2) D. Arthur and Walls

原文：http://blog.csdn.net/u014800748/article/details/44677483