[LeetCode] 130. Surrounded Regions

轉自LeetCode

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.

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

<Solution>
這題是滿標準的 DFS 題目，只不過從哪裡開始做 DFS 要慎選一下

題目是要求找到被環繞，即上下左右被 X 包圍的區塊

如果直接去找被包圍的區塊，然後判斷它有沒有連到邊緣，這樣會複雜許多

反之，直接找到開放的區塊，也就是從在四條邊緣上的O開始找起

把開放區塊轉換成另一個字元，最後剩下來的O就是要變成X的

code 如下
c++

	class Solution {
	public:
	void solve(vector<vector<char>>& board) {
	if(board.size() == 0) {
	return;
	}
	const int rowNum = board.size();
	const int colNum = board[0].size();
	//>> use DFS to find open area
	//>> only from the edges of board
	for(int c = 0; c < colNum; c++) {
	if(board[0][c] == 'O') {
	DFS(0, c, board);
	}
	if(board[rowNum-1][c] == 'O') {
	DFS(rowNum-1, c, board);
	}
	}
	for(int r = 0; r < rowNum; r++) {
	if(board[r][0] == 'O') {
	DFS(r, 0, board);
	}
	if(board[r][colNum-1] == 'O') {
	DFS(r, colNum-1, board);
	}
	}
	//>> flip
	for(auto &v : board) {
	for(auto &c : v) {
	if(c == 'F') {
	c = 'O';
	}
	else if(c == 'O') {
	c = 'X';
	}
	}
	}
	}
	void DFS(const int &row, const int &col, vector<vector<char>> &board) {
	board[row][col] = 'F';
	//>> up
	if(row > 0 && board[row-1][col] == 'O') {
	DFS(row-1, col, board);
	}
	//>> down
	if((row+1) < board.size() && board[row+1][col] == 'O') {
	DFS(row+1, col, board);
	}
	//>> left
	if(col > 0 && board[row][col-1] == 'O') {
	DFS(row, col-1, board);
	}
	//>>right
	if((col+1) < board[0].size() && board[row][col+1] == 'O') {
	DFS(row, col+1, board);
	}
	}
	};

view raw findSurroundedRegions.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	fun solve(board: Array<CharArray>): Unit {
	for(r in board.indices) {
	if(board[r][0] == 'O') {
	dfs(r, 0, board)
	}
	if(board[r][board[0].lastIndex] == 'O') {
	dfs(r, board[0].lastIndex, board)
	}
	}
	for(c in board[0].indices) {
	if(board[0][c] == 'O') {
	dfs(0, c, board)
	}
	if(board[board.lastIndex][c] == 'O') {
	dfs(board.lastIndex, c, board)
	}
	}
	for(r in board.indices) {
	for(c in board[0].indices) {
	if(board[r][c] == 'O') {
	board[r][c] = 'X'
	} else if (board[r][c] == 'N') {
	board[r][c] = 'O'
	}
	}
	}
	}
	fun dfs(row: Int, col: Int, board: Array<CharArray>) {
	board[row][col] = 'N'
	if(row > 0 && board[row-1][col] == 'O') {
	dfs(row-1,col,board)
	}
	if(row < board.lastIndex && board[row+1][col] == 'O') {
	dfs(row+1,col,board)
	}
	if(col > 0 && board[row][col-1] == 'O') {
	dfs(row,col-1,board)
	}
	if(col < board[0].lastIndex && board[row][col+1] == 'O') {
	dfs(row,col+1,board)
	}
	}
	}

view raw surrounded_regions.kt hosted with ❤ by GitHub