LeetCode: 130. Surrounded Regions

LeetCode: 130. Surrounded Regions

忙于毕设和工作,很久没有更新了……

题目描述

Given a 2D board containing 'X' and 'O' (the letter O), capture all regions surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

Example:

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

Explanation:

Surrounded regions shouldn’t be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any ‘O’ that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.

题目大意: 将给定的 "O", "X" 构成的矩阵中,被 X 包围的 O 反转为 X

解题思路

将边界连通的 O 标记,然后将没有标记的 O 都反转为 X 即可。
如:

X O O X X
O X O O X
X O X X X
X O O O X
X X X X X

对边界连通的 O 进行标记:

X  -O -O  X X
-O  X -O -O X
X   O  X  X X
X   O  O  O X
X   X  X  X X

然后将没标记的 O 反转为 X, 并清除标记的 O 的标记。

X O O X X
O X O O X
X X X X X
X X X X X
X X X X X

AC 代码

class Solution {
private:
    // 将边界的 ‘O’ 标记
    void FlagBorder(vector<vector<char>>& board, int x, int y)
    {
        const static int dirs[][2] = {{1,0}, {0,1}, {-1, 0}, {0, -1}};

        if(board[x][y] == 'X' || board[x][y] == -'O') return;
        else board[x][y] = -'O';

        for(int i = 0; i < 4; ++i)
        {
            int tx = x + dirs[i][0];
            int ty = y + dirs[i][1];

            if(tx < 0 || tx >= board.size() || ty < 0 || ty >= board[0].size())
            {
                continue;
            }

            FlagBorder(board, tx, ty);
        }
    }
public:
    void solve(vector<vector<char>>& board) {

        if(board.empty() || board[0].empty()) return;

        // 标记边界
        for(int i = 0; i < board.size(); ++i)
        {
            FlagBorder(board, i, 0);
            FlagBorder(board, i, board[0].size()-1);
        }
        for(int i = 0; i < board[0].size(); ++i)
        {
            FlagBorder(board, 0, i);
            FlagBorder(board, board.size()-1, i);
        }

        // 统计边界和非边界
        for(int i = 0; i < board.size(); ++i)
        {
            for(int j = 0; j < board[0].size(); ++j)
            {
                if(board[i][j] == 'O') board[i][j] = 'X';          // 没标记的 'O' 反转为 'X' 
                else if(board[i][j] == -'O') board[i][j] = 'O';    // 标记的 'O' 清除标记
            }
        }
    }
};
全部评论

相关推荐

机械打工仔:不管啥专业,找工作改简历的第一课先把你那排版改了,简历上不要写个人简历四个字,找你要简历的谁不知道这个是简历?而且还占那么多空间,直接把自己名字和基础信息写上面,整体字体大一些。 还有这种经典两页简历一页大空白,导出PDF的时候多了一页几乎全是白的你自己看着不难受吗随手的事为啥不能改掉呢,这是态度问题,你试想一下你是HR你打开简历看到格式都没调整过会是什么感受?你自己都不重视你的简历,HR更不会在意。 然后内容你那个做两年咖啡就别往里写了,简历在精不在多,你在往你的简历里打字的时候就要想好这东西对你要找的工作有没有帮助。自我评价写一行就行了,不如给专业技能单开一栏。核心课程均分90这个真别写了,把你上过的有用的专业课列出来也行。有很多地方废话很多的精炼一下,比如你校内项目第一个写的那些,全然没有重点。 好好修改一下,我看你内容也挺优秀的,别被一个随便做的简历耽误了,我一个同专业的打工人看了都揪心更别说一天看几百份简历的HR
听劝,我这个简历该怎么改...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务