[Leetcode][python]Surrounded Regions/被围绕的区域

小灰灰 2022-06-05 03:11 175阅读 0赞

## 题目大意 ##

有一个二维的面板，上面由”X”或者”O”填充。现在要求将被”X”包围的”O”都改成”X”。

## 解题思路 ##

参考：  
[https://shenjie1993.gitbooks.io/leetcode-python/130%20Surrounded%20Regions.html][https_shenjie1993.gitbooks.io_leetcode-python_130_20Surrounded_20Regions.html]

直接去找被X包围的O比较麻烦，不如转换一下思路，找出哪些O是没有被X包围的。

首先在面板四周的O肯定是没有被X包围的，与它们相连的O也是没有被包围的，其它的O都是被X包围的。

问题简化为将与四周的O相连的O都找出来，这些点不用变，其它点都变为X。

首先将四周的O压入栈内，依次访问栈内元素，并将它们标记，接着去判断它们四周的元素是否也是O，如果是且没有被标记过，则将其压入栈中。

当遍历完栈中的元素后，将有标记的元素变为O，其余都是X。

## 代码 ##

class Solution(object):
        def solve(self, board):
            """
            :type board: List[List[str]]
            :rtype: void Do not return anything, modify board in-place instead.
            """
            if not board or not board[0]:
                return
            n = len(board)
            m = len(board[0])
            queue = []
            # 保存所有位于边缘的O
            for i in range(n):
                for j in range(m):
                    if ((i in (0, n - 1)) or (j in (0, m - 1))) and board[i][j] == 'O':  # i in (0, n - 1) 最上面和最下面两排
                        queue.append((i, j))
                        print (i,j)
            # 保存所有与边缘O相连的O
            while queue:
                r, c = queue.pop(0)  # i, j = r, c
                if 0 <= r < n and 0 <= c < m and board[r][c] == 'O':
                    board[r][c] = 'M'  # 变为M的则是不需要变成X的
                    if r - 1 >= 0 and board[r - 1][c] == 'O':
                        queue.append((r - 1, c))
                    if r + 1 < n and board[r + 1][c] == 'O':
                        queue.append((r + 1, c))
                    if c - 1 >= 0 and board[r][c - 1] == 'O':
                        queue.append((r, c - 1))
                    if c + 1 < m and board[r][c + 1] == 'O':
                        queue.append((r, c + 1))
            # 重新更新棋盘
            for i in range(n):
                for j in range(m):
                    if board[i][j] == 'M':
                        board[i][j] = 'O'
                    else:
                        board[i][j] = 'X'

## 总结 ##

还可以用union-find法  
[https://blog.csdn.net/guoziqing506/article/details/78752557][https_blog.csdn.net_guoziqing506_article_details_78752557]

[https_shenjie1993.gitbooks.io_leetcode-python_130_20Surrounded_20Regions.html]: https://shenjie1993.gitbooks.io/leetcode-python/130%20Surrounded%20Regions.html
[https_blog.csdn.net_guoziqing506_article_details_78752557]: https://blog.csdn.net/guoziqing506/article/details/78752557