深度优先搜索之被围绕的区域
深度优先搜索之被围绕的区域
问题:
本题的意思被包围的区间不会存在于边界上所以边界上的O以及与O联通的都不算做包围,只要把边界上的O以及与之联通的O 进行特殊处理,剩下的O替换成X即可,故问题转化为,如何寻找和边界联通的O,我们需要考虑如下情况。 X X X X X O O X X X O X X O O X 从每一个边缘的O开始,只要和边缘的O联通,则它就没有被包围。 1.首先寻找边上的每一个O,如果没有,表示所有的O都被包围 2.对于边上的每一个O进行dfs进行扩散,先把边上的每一个O用特殊符号标记,比如*,#等, 3.把和它相邻的O都替换为特殊符号,每一个新的位置都做相同的dfs操作. 4.所有扩散结束之后,把特殊符号的位置(和边界连通)还原为O,原来为O的位置(和边界不连通)替换为X即可。
代码:
class Solution {
//四个方向顺时针更新
in
深度优先搜索之被围绕的区域最先出现在Python成神之路。
共有 0 条评论