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/

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容