C++LeetCode 구현(130.포위 영역)

[LeetCode]130.주변 지역 포위 지역
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.
이것 은 XXOO 에 관 한 문제 입 니 다.약간 바둑 같 습 니 다.싸 인 O 를 모두 X 로 만 들 었 지만 다른 것 은 가장자리 의 O 가 포위 되 지 않 았 습 니 다.이전 과 같 습 니 다.  Number of Islands  비슷 해 요.DFS 로 다 풀 수 있어 요.처음에 DFS 가 중간 에 널 려 있 는 O 가 가장자리 에 도달 하지 않 으 면 모두 X 가 되 고 가장자리 에 도달 하면 그 전에 X 가 된 것 을 다시 되 돌려 주 는 것 이 제 생각 이 었 습 니 다.그러나 이렇게 하 는 것 은 매우 불편 하 다.인터넷 에서 흔히 볼 수 있 는 방법 은 행렬 의 네 변 을 스 캔 하 는 것 이다.만약 에 O 가 있 으 면 DFS 로 옮 겨 다 니 며 연 결 된 O 를 모두 다른 문자 로 바 꾸 는 것 이다.예 를 들 어\$,이렇게 나머지 O 는 모두 포위 되 었 다.그리고 이 O 를 X 로 바 꾸 고$를 O 로 바 꾸 면 된다.코드 는 다음 과 같 습 니 다:
해법 1:

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 > 0 && board[i][j - 1] == 'O') 
                solveDFS(board, i, j - 1);
        }
    }
};

옛날 에 위의 코드 중 마지막 if 는 j>0 이 아니 라 j>1 이 어야 했 습 니 다.왜 j>0 은 OJ 의 마지막 빅 데 이 터 를 통 해 집합 할 수 없 었 습 니까?블 로 거들 은 그 비밀 을 모 르 기 시 작 했 습 니 다.다른 네티즌 에 게 로 컬 기기 에서 마지막 빅 데 이 터 를 통 해 집합 할 수 있다 는 주 의 를 받 을 때 까지 블 로 거들 도 프로그램 을 써 서 검 증 했 습 니 다.참고 하 세 요LeetCode Surrounded Regions 포위 구역 의 DFS 방법 검증.j>0 이 정확 하 다 는 것 을 발견 하면 같은 결 과 를 얻 을 수 있 습 니 다.신기 한 것 은 지금 j>0 으로  OJ 도 통과 할 수 있어.
다음 과 같은 해법 은 DFS 해법 입 니 다.재 귀 함수 의 쓰기 만 약간 다 르 지만 본질 적 으로 큰 차이 가 없습니다.코드 는 다음 과 같 습 니 다.
해법 2:

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);
            }
        }
    }
};

우 리 는 교 체 된 해법 을 사용 할 수 있 지만 전체적인 사고방식 은 똑같다.경계 에 있 는 O 를 찾 은 후에 대기 열 queue 를 이용 하여 BFS 로 연 결 된 모든 O 를 찾 은 다음 에 달러 번 호 를 표시 한다.마지막 처 리 는 먼저 모든 O 를 X 로 바 꾼 다음 에 달러 번 호 를 O 로 바 꾸 면 됩 니 다.코드 는 다음 과 같 습 니 다.
해법 3:

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) continue;
                if (board[i][j] != 'O') continue;
                board[i][j] = '$';
                queue<int> q{{i * n + j}};
                while (!q.empty()) {
                    int t = q.front(), x = t / n, y = t % n; q.pop();
                    if (x >= 1 && board[x - 1][y] == 'O') {board[x - 1][y] = '$'; q.push(t - n);}
                    if (x < m - 1 && board[x + 1][y] == 'O') {board[x + 1][y] = '$'; q.push(t + n);}
                    if (y >= 1 && board[x][y - 1] == 'O') {board[x][y - 1] = '$'; q.push(t - 1);}
                    if (y < n - 1 && board[x][y + 1] == 'O') {board[x][y + 1] = '$'; q.push(t + 1);}
                }
            }
        }
        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';
            }
        }
    }
};

Github 동기 화 주소:
https://github.com/grandyang/leetcode/issues/130
유사 한 제목:
Number of Islands
Walls and Gates
참고 자료:
https://leetcode.com/problems/surrounded-regions/
https://leetcode.com/problems/surrounded-regions/discuss/41895/Share-my-clean-Java-Code
https://leetcode.com/problems/surrounded-regions/discuss/41825/Simple-BFS-solution-easy-to-understand
https://leetcode.com/problems/surrounded-regions/discuss/41612/A-really-simple-and-readable-C%2B%2B-solutionuff0conly-cost-12ms
C++구현 LeetCode(130.포위 구역)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 포위 구역 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 찾 아 보 세 요.앞으로 많은 응원 부 탁 드 리 겠 습 니 다!