被围绕的区域c++

题目

 链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网

输入

4 4
XXXX
XOOX
XOXX
XXOX

 输出

XXXX
XXXX
XXXX
XXOX

思路

 由题知边界上的"O"和 与边界的"O"相连的"O"不会被标记，我们可以用一个数组st[][]标记这些区域。然后未被标记的都输出为"X"。标记的方法是深度优先搜索或者广度优先搜索。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 210;
bool st[N][N];//标记某块区域是否会被填充为"X"
string s[N];
int n, m;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

void dfs(int x, int y)
{
    st[x][y] = true;
    
    for (int i = 0; i < 4; i ++)
    {
        int tx = x + dx[i], ty = y + dy[i];
        if (tx >= 0 && tx < n && ty >= 0 && ty < m && !st[tx][ty] && s[tx][ty] == 'O')
        dfs(tx, ty);
    }
}


int main()
{
    cin >> n >> m;
    
    for (int i = 0; i < n; i ++)
        cin >> s[i];
    
    for (int i = 0; i < m; i ++)
        if (!st[0][i] && s[0][i] == 'O')
            dfs(0, i);
    
    for (int i = 0; i < n; i ++)
        if (!st[i][m - 1] && s[i][m - 1] == 'O')
            dfs(i, m - 1);
            
    for (int i = m - 1; i >= 0; i --)
        if (!st[n - 1][i] && s[n - 1][i] == 'O')
        dfs(n - 1, i);
    
    for (int i = n - 1; i >= 0; i --)
        if (!st[i][0] && s[i][0] == 'O')
        dfs(i, 0);
    
    for (int i = 0; i < n; i ++)
    {
        for (int j = 0; j < m; j ++)
            if (!st[i][j])
                cout << "X";
        else cout << "O";
        puts("");
    }
    return 0;
}