【题目描述】
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'。
【参考答案】