LeetCode 130. Surrounded Regions
Description
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.
描述
給定一個(gè)二維的矩陣朦乏，包含 'X' 和 'O'（字母 O）户盯。
找到所有被 'X' 圍繞的區(qū)域烤黍，并將這些區(qū)域里所有的 'O' 用 'X' 填充赵誓。
示例:
X X X X
X O O X
X X O X
X O X X
運(yùn)行你的函數(shù)后，矩陣變?yōu)椋?/p>
X X X X
X X X X
X X X X
X O X X
解釋:
被圍繞的區(qū)間不會(huì)存在于邊界上司恳，換句話說(shuō)途乃，任何邊界上的 'O' 都不會(huì)被填充為 'X'。 任何不在邊界上扔傅，或不與邊界上的 'O' 相連的 'O' 最終都會(huì)被填充為 'X'耍共。如果兩個(gè)元素在水平或垂直方向相鄰烫饼，則稱(chēng)它們是“相連”的。
思路
- 此題目使用了深度優(yōu)先搜索.
- 我們檢查矩陣的第一行试读，最后一行杠纵，第一列，最后一列有沒(méi)有"O",如果有钩骇，我們從此位置進(jìn)行深度優(yōu)先遍歷比藻，將從此位置開(kāi)始所有連續(xù)的"O"都置為一個(gè)標(biāo)記元素,如"1".
- 然后我們?cè)谶M(jìn)行遍歷，將所有的"1"都置為"O"倘屹，其他元素都置為"X".
# -*- coding: utf-8 -*-
# @Author: 何睿
# @Create Date: 2019-01-05 22:10:17
# @Last Modified by: 何睿
# @Last Modified time: 2019-01-06 14:25:42
from pprint import pprint
class Solution:
def solve(self, board):
"""
:type board: List[List[str]]
:rtype: void Do not return anything, modify board in-place instead.
"""
# 如果矩陣為空银亲，則直接返回
if not board:
return
# 獲取矩陣行數(shù)和列數(shù)
row, col = len(board), len(board[0])
# 遍歷第一行和最后一行
for i in range(0, row):
# 如果當(dāng)前的元素為"O",則進(jìn)行深度優(yōu)先遍歷，將所有的"O"都置為"1"
# （或者其他標(biāo)記元素纽匙，只要不是"X"或"O"即可）
# 檢查第一行的所有元素
if board[i][0] == "O":
self.dfs(board, i, 0, row, col)
# 檢查最后一行的所有元素
if board[i][col-1] == 'O':
self.dfs(board, i, col-1, row, col)
# 同上务蝠，遍歷第一列和最后一列的所有元素
for i in range(1, col-1):
if board[0][i] == 'O':
self.dfs(board, 0, i, row, col)
if board[row-1][i] == 'O':
self.dfs(board, row-1, i, row, col)
# 遍歷所有元素，將剛才標(biāo)記的元素置為"O",其他元素都置為"X"
for i in range(0, row):
for j in range(0, col):
if board[i][j] == "1":
board[i][j] = "O"
else:
board[i][j] = "X"
def dfs(self, board, row, col, rows, cols):
# 遞歸結(jié)束條件烛缔，如果已經(jīng)越界則結(jié)束遞歸
if row >= rows or col >= cols or row < 0 or col < 0:
return
# 如果當(dāng)前元素是"O",則置為標(biāo)記元素"1"
if board[row][col] == "O":
board[row][col] = '1'
# 進(jìn)行深度優(yōu)先遍歷馏段，一共有上下左右四個(gè)出口
self.dfs(board, row+1, col, rows, cols)
self.dfs(board, row-1, col, rows, cols)
self.dfs(board, row, col+1, rows, cols)
self.dfs(board, row, col-1, rows, cols)
源代碼文件在這里.
?本文首發(fā)于何睿的博客，歡迎轉(zhuǎn)載践瓷，轉(zhuǎn)載需保留文章來(lái)源院喜，作者信息和本聲明.
