Surrounded Regions

原题: https://leetcode.com/problems/surrounded-regions/description/

题意: 输入一个二维矩阵,把所有被X包围的O都变成X,但如果某个O在边(角)上,则所有与这个O相连的O都不能变成X。

例子: 

给定:
X X X X
X O O X
X X O X
X O X X
返回:
X X X X
X X X X
X X X X
X O X X

标签: surrounded、regions、包围、一个二维、相连、面试
猜你感兴趣的圈子:
LeetCode交流圈
  • Bingo
    2017-08-13 11:15:58 1楼#1层
    C++解法一:
    class Solution {
    public:
        void solve(vector<vector<char> >& board) {
            for (int i = 0; i < board.size(); ++i) {
                for (int j = 0; j < board[i].size(); ++j) {
                    if ((i == 0 || i == board.size() - 1 || j == 0 || j == board[i].size() - 1) && board[i][j] == 'O')
                        solveDFS(board, i, j);
                }
            }
            for (int i = 0; i < board.size(); ++i) {
                for (int j = 0; j < board[i].size(); ++j) {
                    if (board[i][j] == 'O') board[i][j] = 'X';
                    if (board[i][j] == '$') board[i][j] = 'O';
                }
            }
        }
        void solveDFS(vector<vector<char> > &board, int i, int j) {
            if (board[i][j] == 'O') {
                board[i][j] = '$';
                if (i > 0 && board[i - 1][j] == 'O') 
                    solveDFS(board, i - 1, j);
                if (j < board[i].size() - 1 && board[i][j + 1] == 'O') 
                    solveDFS(board, i, j + 1);
                if (i < board.size() - 1 && board[i + 1][j] == 'O') 
                    solveDFS(board, i + 1, j);
                if (j > 1 && board[i][j - 1] == 'O') 
                    solveDFS(board, i, j - 1);
            }
        }
    };
  • Bingo
    2017-08-13 11:16:19 2楼#1层
    C++解法二:
    class Solution {
    public:
        void solve(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);
                }
            }
        }
    };
  • 回复
隐藏