Leetcode題解 Python & C#：六月挑戰DAY17 Surrounded Regions

給一個二維的串列，其元素為 'X' 或 'O' 要把所有 'O' 被 'X' 包圍的換成 'X'。

這規則有點像圍棋，圍住就吃掉。

那有好幾種思路：

最直觀的，就是遇到一個 'O' 時，檢查其四周是否為 'X'，然後如果檢查時遇到 'O'，就延伸檢查。

或者變體，直接檢查 'O' 的上下左右到邊際是否有 'X' 出現，然後給標記，最後檢查標記四周只有標記與 'X'，就換成 'X'。

走到這裡，只有一種狀況會需要特別小心，就是在邊際的 'O' ，如果有碰到，就會產生要當心的狀況。

換個思考，與其費心找四周，不如把邊際或與之相連的 'O' 抓出來，其他都改成 'X' 即可。

Python

class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """        
        if not board or not board[0]: return 
        excludePos = set()
        rows = len(board)
        cols = len(board[0])
        
        def searchExclude(y, x):
            if y < 0 or y >= rows: return
            if x < 0 or x >= cols: return
            
            if board[y][x] == "O" and (y,x) not in excludePos:
                excludePos.add((y,x))
                searchExclude(y-1, x)
                searchExclude(y+1, x)
                searchExclude(y, x-1)
                searchExclude(y, x+1)
                
        for y in range(rows):
            searchExclude(y, 0)
            searchExclude(y, cols-1)
            
        for x in range(cols):
            searchExclude(0, x)
            searchExclude(rows-1, x)       
            
        for x in range(1, cols-1):
            for y in range(1, rows-1):
                if board[y][x] == "O" and (y,x) not in excludePos:
                    board[y][x] = "X"

C#

public class Solution {
    public int rows;
    public int cols;
    public HashSet<(int, int)> excludePos;
    
    public void Solve(char[][] board) {
        rows = board.Length;
        if(rows == 0){return;}
        cols = board[0].Length;
        if(cols == 0){return;}    
        excludePos = new HashSet<(int, int)>();
            
        for(int y = 0; y < rows; y++)
        {
            SearchExcluded(board, y, 0);
            SearchExcluded(board, y, cols-1);            
        }        
        for(int x = 0; x < cols; x++)
        {
            SearchExcluded(board, 0, x);
            SearchExcluded(board, rows-1, x);            
        } 
        
        for(int y = 0; y < rows; y++)
        {
            for(int x = 0; x < cols; x++)
            {
                if(board[y][x] == 'O' && !excludePos.Contains((y, x)))
                {
                    board[y][x] = 'X';
                }
            }
        }
    }
    
    public void SearchExcluded(char[][] board, int y, int x) {
        if(y < 0 || y >= rows){return;}
        if(x < 0 || x >= cols){return;}     
        if(board[y][x] == 'O' && !excludePos.Contains((y, x)))
        {
            excludePos.Add((y, x));
            SearchExcluded(board, y-1, x);
            SearchExcluded(board, y+1, x);
            SearchExcluded(board, y, x-1);
            SearchExcluded(board, y, x+1);
        }
    }
}