【Henu ACM Round#18 F】Arthur and Walls

【链接】 我是链接,点我呀:)

【题意】

在这里输入题意

【题解】

考虑,为什么一个连通块里面的空格没有变成一个矩形?
如果不是形成矩形的话。
肯定是因为某个2x2的单张方形里面。
只有一个角是墙。其他角都是空的正方形。
举一些例子。
```
...*
*...
```
可以看到这个连通块不是长方形。
就是因为有
```
..
*.
```
和
```
.*
..
```
如果我们把这两个角上的墙给删掉的话。
显然就能得到一个矩形了。

根据这个作为启发。

我们可以将整张图里面所有的2x2的正方形里面的"角"都给删掉。

这样的话,就能保证最后的图形所有的空格连通块是矩形了。

所以这样的"角"是连通块"不是矩形"的充分必要条件。

我们把所有的"角"都去掉,那么剩下的空格连通块就一定是矩形了。

改变了一个角之后。要注意看看和它相邻的4个2x2张方形有没有变成"角"

【代码】

#include <bits/stdc++.h>

using namespace std;

const int N = 2000;

int n,m,a[N+10][N+10];

char s[N+10][N+10];

void dfs(int x,int y){

    if (x<1 || x >= n || y<1 || y >= m) return;

    int cnt = 0;

    int tx,ty;//墙的坐标

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

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

            if (s[x+i][y+j]=='*'){

                cnt++;

                tx = x+i,ty = y+j;

            }

    if (cnt==1){

        s[tx][ty]='.';

        dfs(tx-1,ty-1);

        dfs(tx,ty-1);

        dfs(tx-1,ty);

        dfs(tx,ty);

    }

}

int main(){

	#ifdef LOCAL_DEFINE

	    freopen("rush_in.txt", "r", stdin);

	#endif

	ios::sync_with_stdio(0),cin.tie(0);

    cin >> n >> m;

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

        cin >>(s[i]+1);

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

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

            dfs(i,j);//(i,j)是左上角的坐标

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

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

            cout<<s[i][j];

        }

        cout<<endl;

    }

	return 0;

}