博文中会简要介绍Leetcode P0130题目分析及解题思路。
“Surrounded Regions”这道题比较基础，主要考察的就是广度优先搜索。以在四条边上的每个”O”为起点分别做BFS遍历矩阵，将所有与其相邻相连的”O”的位置标记为不可翻转，最后再遍历一遍矩阵，翻转那些未被标记的”O”即可。
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 XAfter running your function, the board should be:
X X X X X X X X X X X X X O X XExplanation:
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.
以下是Java的题解代码实现。
class Solution {
class Coord {
int row;
int col;
public Coord(int r, int c) {
this.row = r;
this.col = c;
}
@Override
public int hashCode() {
return row*11+col;
}
@Override
public boolean equals(Object o) {
if (o == null)
return false;
else if (o instanceof Coord) {
Coord temp = (Coord) o;
return (temp.row == this.row) && (temp.col == this.col);
}
else
return false;
}
@Override
public String toString() {
return this.row+","+this.col;
}
}
private int[] dr = new int[] {-1, 0, 1, 0};
private int[] dc = new int[] {0, 1, 0, -1};
public void solve(char[][] board) {
if (board.length == 0 || board[0].length == 0)
return;
int H = board.length, W = board[0].length;
Set<Coord> letterOs = new HashSet<>();
List<Coord> borderOs = new ArrayList<>();
for (int r=0; r<H; ++r) {
for (int c=0; c<W; ++c) {
if (board[r][c] == 'O') {
Coord temp = new Coord(r, c);
letterOs.add(temp);
if (r == 0 || r == H-1 || c == 0 || c == W-1)
borderOs.add(temp);
}
}
}
// BFS
for (Coord borderO: borderOs) {
if (!letterOs.contains(borderO))
continue;
Queue<Coord> queue = new LinkedList<>();
queue.offer(borderO);
letterOs.remove(borderO);
while (!queue.isEmpty()) {
Coord pos = queue.poll();
for (int di=0; di<4; ++di) {
int nextR = pos.row+dr[di];
int nextC = pos.col+dc[di];
if (nextR >= 0 && nextR < H
&& nextC >= 0 && nextC < W
&& board[nextR][nextC] == 'O') {
Coord temp = new Coord(nextR, nextC);
// Not visited
if (letterOs.contains(temp)) {
queue.offer(new Coord(nextR, nextC));
letterOs.remove(temp);
}
}
}
}
}
// Flip
for (Coord o: letterOs) {
board[o.row][o.col] = 'X';
}
}
}
以下是C++的题解代码实现。
class Solution {
public:
void solve(vector<vector<char>>& board) {
if (board.size() == 0 || board[0].size() == 0) {
return;
}
int height = board.size();
int width = board[0].size();
// Get all regions that cannot be flipped
vector<vector<bool>> unflipped(height, vector<bool>(width, false));
this->_BorderCheck(board, unflipped);
for (int i1=0; i1<height; ++i1) {
for (int j2=0; j2<width; ++j2) {
// Flip
if (board[i1][j2] == 'O' && !unflipped[i1][j2]) {
board[i1][j2] = 'X';
}
}
}
}
private:
// Directions mapping
// int diMove[4][2];
// {-1, 0}, {0, 1}, {1, 0}, {0, -1};
void _BorderCheck(vector<vector<char>> &board, vector<vector<bool>> &unflipped) {
int height = board.size();
int width = board[0].size();
// Check four edges
for (int idx=0; idx<height; ++idx) {
// Left
if (board[idx][0] == 'O' && !unflipped[idx][0]) {
int coord[] = {idx, 0};
this->_Bfs(board, unflipped, coord);
}
// Right
if (board[idx][width-1] == 'O' && !unflipped[idx][width-1]) {
int coord[] = {idx, width-1};
this->_Bfs(board, unflipped, coord);
}
}
for (int idx=0; idx<width; ++idx) {
// Up
if (board[0][idx] == 'O' && !unflipped[0][idx]) {
int coord[] = {0, idx};
this->_Bfs(board, unflipped, coord);
}
// Down
if (board[height-1][idx] == 'O' && !unflipped[height-1][idx]) {
int coord[] = {height-1, idx};
this->_Bfs(board, unflipped, coord);
}
}
}
void _Bfs(vector<vector<char>> &board, vector<vector<bool>> &unflipped,
int *coord) {
queue<int*> coord_queue;
coord_queue.push(coord);
int height = board.size();
int width = board[0].size();
while (!coord_queue.empty()) {
int *curr = coord_queue.front();
coord_queue.pop();
unflipped[curr[0]][curr[1]] = true;
// Add Children
for (int di=0; di<4; ++di) {
int x = curr[0]+this->diMove[di][0];
int y = curr[1]+this->diMove[di][1];
// Check the constraints
if (x >= 0 && x < height && y >= 0 && y < width
&& board[x][y] == 'O'
&& !unflipped[x][y]) {
int *new_coord = new int [2];
new_coord[0] = x;
new_coord[1] = y;
unflipped[x][y] = true;
coord_queue.push(new_coord);
}
}
}
}
};