Surrounded Region@leetcode

刷题必备书籍：Cracking the Coding Interview: 150 Programming Questions and Solutions 

简历：The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍：Introduction to Algorithms
编程珠玑：Programming Pearls (2nd Edition)
C++ 学习：The C++ Programming Language, 4th Edition
经典操作系统书籍，龙书：Operating System Concepts
创业：The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career

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 .

For example,

X X X X
X O O X
X X O X
X O X X

After running your function, the board should be:

X X X X
X X X X
X X X X
X O X X

» Solve this problem

这道题的关键是第一弄清楚：1。哪些o是需要被替代的，哪些不是。 2. 如何确定那些要被替代的。

思路1. dfs
不能被替代的o就是和边界相接的o，所以我们用dfs来搜索，只搜索边界，遇到边界的o mark为d，然后搜索和这个o相接的o，一直搜索到底。写一个单独的dfs的函数。这个可以在board上原地操作，不需要additional space.

大集合超时过不了。

2.bfs
需要用一个queue来存node。貌似有些复杂，就不写了