###### tags: `Leetcode` `medium` `bfs` `dfs` `python`

# 130. Surrounded Regions

## [題目連結:] https://leetcode.com/problems/surrounded-regions/

## 題目:
Given an ```m x n``` matrix ```board``` containing ```'X' and 'O'```, capture all regions that are 4-directionally surrounded by ```'X'```.

A region is **captured** by flipping all ```'O's into 'X's``` in that surrounded region.


#### [圖片來源:] https://leetcode.com/problems/surrounded-regions/

## 解題想法:
* 題目為:求將被'x'圍起來的'o'全變'x'
* 周圍的'o'保持不用變
* 解法: 先找四周邊界的'o' 在看其延伸出去是否為'o'
* 若有 :則其延伸出去的'o'全保持
* 若沒有:則將內部全填為'x'

## Python:

class Solution(object):
    def solve(self, board):
        """
        :type board: List[List[str]]
        :rtype: None Do not return anything, modify board in-place instead.
        """
        m=len(board)
        n=len(board[0])
        stack=[]
        #將邊=='0'的位置加入stack
        for i in range(m):
            #左邊
            if board[i][0]=='O':
                stack.append((i,0))
            #右邊
            if board[i][n-1]=='O':
                stack.append((i,n-1))
        for j in range(n):
            #上邊
            if board[0][j]=='O':
                stack.append((0,j))
            #下邊
            if board[m-1][j]=='O':
                stack.append((m-1,j))
        #bfs 紀錄合法的'O'將其標記成'#'
        dirs=[(-1,0),(1,0),(0,1),(0,-1)]
        while stack:
            curX,curY=stack.pop(0)
            #確保在邊界內，且代表此O不可被變動 但要繼續找鄰居 所以先此位子的O更換符號'#'
            if 0<=curX<m and 0<=curY<n and board[curX][curY]=='O':
                board[curX][curY]='#'
                #將其四邊加入stack
                for dirX,dirY in dirs:
                    stack.append((curX+dirX,curY+dirY))

        #填將非'#'都改為'X','#'改為'O'
        for i in range(m):
            for j in range(n):
                board[i][j]='O' if board[i][j]=='#' else 'X'

result = Solution()
board = [["X","X","X","X"],
         ["X","O","O","X"],
         ["X","X","O","X"],
         ["X","O","X","X"]]
print('Original:',board)
result.solve(board)
print('New:',board)

'''
Original: [['X', 'X', 'X', 'X'], 
           ['X', 'O', 'O', 'X'], 
           ['X', 'X', 'O', 'X'], 
           ['X', 'O', 'X', 'X']]

New:      [['X', 'X', 'X', 'X'], 
           ['X', 'X', 'X', 'X'], 
           ['X', 'X', 'X', 'X'], 
           ['X', 'O', 'X', 'X']]
'''