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' 清除标记
            }
        }
    }
};
全部评论

相关推荐

07-11 22:27
中南大学 Java
程序员牛肉:学历的话没问题。但是没问题的也就只有学历了。 其实你的整体架构是正确的,博客接着干。但是项目有点过于简单了。从后端的角度上讲,你这也就是刚入门的水平,所以肯定约面试够呛。 如果你要应聘后端岗位,那你第一个项目竟然是仿写操作系统。这个你要面试官咋问你。你一定要记住一点,你简历上写的所有的东西,都是为了证明你有能力胜任当前的岗位,而不是为了证明你自己会什么。 如果你只是浅浅的做几个项目,描述也都是烂大街。技术点也都是各种混水类的配置类需求,那你就不要幻想自己能走多远。一定要保持思考,保持学习。
点赞 评论 收藏
分享
自学java狠狠赚一...:骗你点star的,港卵公司,记得把star收回去
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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