LeetCode 题解（153）: Surrounded Regions

本文主要是介绍LeetCode 题解（153）: 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.

For 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

题解：

先用BFS把矩形最外面一圈遍历了，将由最外一圈‘O’所能访问到的全部‘O’标记为visited。然后遍历里面元素，遇见未访问过的'O'直接变为‘X’即可。

C++版：

class Solution {
public:void solve(vector<vector<char>>& board) {if(board.size() == 0)return;vector<vector<bool>> visited(board.size(), vector<bool>(board[0].size(), false));for(int j = 0; j < board[0].size(); j++) {visit(board, 0, j, visited);visit(board, board.size()-1, j, visited);}for(int i = 1; i < board.size() - 1; i++) {visit(board, i, 0, visited);visit(board, i, board[0].size()-1, visited);}for(int i = 1; i < board.size() - 1; i++) {for(int j = 1; j < board[0].size() - 1; j++) {if(!visited[i][j]) {visited[i][j] = true;if(board[i][j] == 'O')board[i][j] = 'X';}}}}void enclose(vector<vector<char>>& board, int i, int j, vector<vector<bool>>& visited) {visited[i][j] = true;if(board[i][j] == 'O') {queue<pair<int, int>> q;q.push(pair<int, int>(i, j));while(!q.empty()) {pair<int, int> current = q.front();q.pop();int x = current.first, y = current.second;addQ(board, q, x - 1, y, visited);addQ(board, q, x + 1, y, visited);addQ(board, q, x, y - 1, visited);addQ(board, q, x, y + 1, visited);}}}void addQ(vector<vector<char>>& board, queue<pair<int, int>>& q, int i, int j, vector<vector<bool>>& visited) {if(i < 0 || i >= board.size() || j < 0 || j >= board.size())return;if(board[i][j] == 'O') {if(!visited[i][j]) {visited[i][j] = true;q.push(pair<int, int>(i, j));}}}void visit(vector<vector<char>>& board, int i, int j, vector<vector<bool>>& visited) {if(visited[i][j])return;else {if(board[i][j] == 'O') {enclose(board, i, j, visited);} else {visited[i][j] = true;}}}
};

Java版：

class Position {int i;int j;Position(int x, int y) {i = x; j = y;}
}public class Solution {public void solve(char[][] board) {if(board.length == 0)return;int row = board.length, col = board[0].length;boolean[][] visited = new boolean[row][col];for(int j = 0; j < col; j++) {visit(board, 0, j, visited);visit(board, row-1, j, visited);}for(int i = 1; i < row - 1; i++) {visit(board, i, 0, visited);visit(board, i, col-1, visited);}for(int i = 1; i < row - 1; i++) {for(int j = 1; j < col - 1; j++) {if(!visited[i][j] && board[i][j] == 'O')board[i][j] = 'X';}}}public void visit(char[][] board, int i, int j, boolean[][] visited) {if(!visited[i][j] && board[i][j] == 'O') {enclose(board, i, j, visited);}}public void enclose(char[][] board, int i, int j, boolean[][] visited) {visited[i][j] = true;Queue<Position> q = new LinkedList<Position>();int row = board.length, col = board[0].length;q.add(new Position(i, j));while(q.size() != 0) {Position current = q.poll();int x = current.i, y = current.j;addQ(board, q, row, col, visited, x-1, y);addQ(board, q, row, col, visited, x+1, y);addQ(board, q, row, col, visited, x, y-1);addQ(board, q, row, col, visited, x, y+1);}}public void addQ(char[][] board, Queue<Position> q, int row, int col, boolean[][] visited, int i, int j) {if(i < 0 || j < 0 || i >= row || j >= col)return;if(!visited[i][j] && board[i][j] == 'O') {visited[i][j] = true;q.add(new Position(i, j));}}
}

Python版：

import Queueclass Solution:# @param {character[][]} board# @return {void} Do not return anything, modify board in-place instead.def solve(self, board):if len(board) == 0:returnvisited = [[False for i in range(len(board[0]))] for j in range(len(board))]for j in range(len(board[0])):self.visit(board, 0, j, visited)self.visit(board, len(board) - 1, j, visited)for i in range(1, len(board)-1):self.visit(board, i, 0, visited)self.visit(board, i, len(board[0])-1, visited)for i in range(1, len(board)-1):for j in range(1, len(board[0])-1):if not visited[i][j] and board[i][j] == 'O':board[i][j] = 'X'def visit(self, board, i, j, visited):if board[i][j] == 'O' and not visited[i][j]:self.enclose(board, i, j, visited)def enclose(self, board, i, j, visited):visited[i][j] = Trueq = Queue.Queue()q.put((i, j))while not q.empty():current = q.get()x, y = current[0], current[1]self.addQ(board, visited, x-1, y, q)self.addQ(board, visited, x+1, y, q)self.addQ(board, visited, x, y-1, q)self.addQ(board, visited, x, y+1, q)def addQ(self, board, visited, i, j, q):if i < 0 or j < 0 or i >= len(board) or j >= len(board[0]):returnif board[i][j] == 'O' and not visited[i][j]:visited[i][j] = Trueq.put((i, j))

这篇关于LeetCode 题解（153）: Surrounded Regions的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---