78被围绕的区域（130）

作者: Turbo时间限制: 1S章节: 宽度优先搜索

晚于: 2020-08-26 12:00:00后提交分数乘系数50%

截止日期: 2020-09-02 12:00:00

问题描述 :

给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。

找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

示例:

X X X X

X O O X

X X O X

X O X X

运行后，矩阵变为：

X X X X

X O X X

解释:

被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

输入说明 :

首先输入矩阵的行数m和列数n，

然后输入m行，每行n个字符'X' 或 'O'。中间无空格分隔。

1<=m, n<=200

输出说明 :

输出结果，字符'X' 或 'O'之间无空格。

输入范例 :

4 4 XXXX XOOX XXOX XOXX

输出范例 :

XXXX XXXX XXXX XOXX

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
/*class Solution {
public:
    void solve(vector<vector<char>>& board) {
        
    }
};*/
//反面思想，找出所有与边界相连的O，做个标记，最后遍历没被标记的O 
class Solution {
    int m,n;
public :
    void solve(vector<vector<char>> &board) {
        if(board.size()==0||board[0].size()==0)
            return ;
        m=board.size();
        n=board[0].size();
        for(int i=0;i<m;i++)
        {    
                dfs(board,i,0);//对第一列的O深优 
                dfs(board,i,n-1);//对最后一列深优 
        }
        for(int j=0;j<n;j++){    //对第一列和最后一列的所有O进行深度优先搜索
                dfs(board,0,j);//对第一行的O深优 
                dfs(board,m-1,j);//对最后一行深优 
        }
        for(int i=0;i<m;i++)
        {    //遍历矩阵，将O变为X，将-变为O
            for(int j=0;j<n;j++)
            {
                if(board[i][j]=='O')
                    board[i][j]='X';
                if(board[i][j]=='-')
                    board[i][j]='O';
            }
        }
        return ;
    }
  /**
  * 使用递归进行深度优先搜索
  */
    void dfs(vector<vector<char>> &board,int i,int j){
        if(i<0||j<0||i>=m||j>=n||board[i][j]!='O')   //递归终止条件判断
            return;
        board[i][j]='-';    //将当前O更改为-
            dfs(board,i-1,j);   //递归该点上方的点
            dfs(board,i+1,j);   //递归该点下方的点
            dfs(board,i,j-1);   //递归该点左边的点
            dfs(board,i,j+1);   //递归该点右边的点
        return ;
    }
};

int main()
{
    vector<vector<char> > board;
    int m,n;
    cin>>m;
    cin>>n;

    char ch;
    for(int i=0; i<m; i++)
    {
        vector<char> aLine;
        for(int j=0; j<n; j++)
        {
            cin>>ch;
            aLine.push_back(ch);
        }
        board.push_back(aLine);
    }
    Solution().solve(board);
    for(int i=0; i<board.size(); i++)
    {
        vector<char> aLine = board[i];
        for(int j=0; j<aLine.size(); j++)
            cout<<aLine[j];
        cout<<endl;
    }
    return 0;
}