[LintCode] Surrounded Regions 包围区域

简介:

Given a 2D board containing 'X' and '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 capture all regions surrounded by 'X', the board should be:
X X X X
X X X X
X X X X
X O X X

LeetCode上的原题,请参见我之前的博客Surrounded Regions

解法一:

class Solution {
public:
    /**
     * @param board a 2D board containing 'X' and 'O'
     * @return void
     */
    void surroundedRegions(vector<vector<char>>& board) {
        if (board.empty() || board[0].empty()) return;
        int m = board.size(), n = board[0].size();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                    if (board[i][j] == 'O') dfs(board, i , j);
                }
            }
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                if (board[i][j] == '$') board[i][j] = 'O';
            }
        }
    }
    void dfs(vector<vector<char>> &board, int x, int y) {
        int m = board.size(), n = board[0].size();
        vector<vector<int>> dir{{0,-1},{-1,0},{0,1},{1,0}};
        board[x][y] = '$';
        for (int i = 0; i < dir.size(); ++i) {
            int dx = x + dir[i][0], dy = y + dir[i][1];
            if (dx >= 0 && dx < m && dy >= 0 && dy < n && board[dx][dy] == 'O') {
                dfs(board, dx, dy);
            }
        }
    }
};

解法二:

class Solution {
public:
    /**
     * @param board a 2D board containing 'X' and 'O'
     * @return void
     */
    void surroundedRegions(vector<vector<char>>& board) {
        if (board.empty() || board[0].empty()) return;
        int m = board.size(), n = board[0].size();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i == 0 || i == m - 1 || j == 0 || j == n - 1) {
                    if (board[i][j] == 'O') dfs(board, i , j);
                }
            }
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                if (board[i][j] == '$') board[i][j] = 'O';
            }
        }
    }
    void dfs(vector<vector<char>> &board, int i, int j) {
        int m = board.size(), n = board[0].size();
        if (i < 0 || i >= m || j < 0 || j >= n || board[i][j] != 'O') return;
        board[i][j] = '$';
        dfs(board, i + 1, j);
        dfs(board, i - 1, j);
        dfs(board, i, j + 1);
        dfs(board, i, j - 1);
    }
};

本文转自博客园Grandyang的博客,原文链接:包围区域[LintCode] Surrounded Regions ,如需转载请自行联系原博主。

相关文章
|
1月前
leetcode-1034:边界着色
leetcode-1034:边界着色
20 1
|
6月前
G2Plot Line 线性 x 轴头尾两头不留空白(或指定留白范围)
G2Plot Line 线性 x 轴头尾两头不留空白(或指定留白范围)
45 0
|
7月前
|
算法 数据挖掘 计算机视觉
AcWing 749. 数组的上方区域
AcWing 749. 数组的上方区域
38 0
AcWing 749. 数组的上方区域
AcWing 750. 数组的下方区域
AcWing 750. 数组的下方区域
31 0
AcWing 750. 数组的下方区域
|
存储 算法 前端开发
从一道hard的leetcode到2d包围盒算法
前言 大家好,哈哈哈最近国庆在家无聊比较boring,然后最近也在学习算法,之前我是从来没有做过hard的题目。想着胖虎来挑战下。然后这道题也比较有意思,我不是什么算法大佬,我只是觉得这篇很有意义。读完这篇文章你可以学到什么: 空间中2d包围盒的概念 (boundingBox) 包围盒如何判断是否相交 多个包围盒如何如何联合一个大包围盒的 这就是为什么我要去分享这道题的原因,因为无论在3d或者2d中,你去判断「两个图形是否相交其实快速判断」 就是通过包围盒去做判断, 在游戏中你🤔一下,「一个游戏人物如何判断他是否走到墙壁了」。他是怎么实现碰撞的对吧, 游戏对象 都有一个「精灵」 和 「碰撞
从一道hard的leetcode到2d包围盒算法
Halcon区域region的遍历,合并,旋转与排序
Halcon区域region的遍历,合并,旋转与排序
1312 0
Halcon区域region的遍历,合并,旋转与排序