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 2005int 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;}
大多数人想要改造这个世界，但却罕有人想改造自己。
