Lintcode477 Surrounded Regions solution 题解

【题目描述】

Given a 2D board containing 'X' and 'O', capture all regions surrounded by 'X'.

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

给一个二维的矩阵,包含 'X' 和 'O', 找到所有被 'X' 围绕的区域,并用 'X' 填充满。

【题目链接】

www.lintcode.com/en/problem/surrounded-regions/

【题目解析】

目标是要找到由X包围起来的O的区域。

首先,外围一圈上的O肯定会保留下来。然后,从外围的O能达到的O也要保留。剩下其他的O就是内部的O。所以方法就是从外围的一圈进行DFS算法:依次对外圈的“O”做DFS,将其可以到达O临时设置为#。

特殊用例:只有外围轮廓没有内部。比如长或者宽小于2,此时不存在被包围的'X'。

【参考答案】

www.jiuzhang.com/solutions/surrounded-regions/

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 14,358评论 0 33
  • rljs by sennchi Timeline of History Part One The Cognitiv...
    sennchi阅读 12,183评论 0 10
  • 题目 Given a 2D board containing 'X' and 'O' (the letter O)...
    时光杂货店阅读 1,603评论 0 0
  • 有一天特别想吃瓜子,甜的。请张师傅买的。也许是十块钱的,第二天微信给了20的红包。过来又被转过来了。 我想以后不会...
    空灵人生阅读 1,184评论 0 0

友情链接更多精彩内容