Surrounded Regions
Total Accepted: 4258 Total
Submissions: 30340My Submissions
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
本题关键是理解问题的特点：四面的最外层搜索，有O通路的就为不被包围的区域，其他都可以置为X；
没把握这个特点，难度为五星级的。
知道这个特点，难度瞬间变为3到4星级。
//2014-2-18 update
const static char NON_SURROUNDED = '*';
void solve(vector<vector<char>> &board)
{
if (board.empty() || board[0].empty()) return;
for (int i = 0; i < board.size(); i++)
{
backtrack(board, i, 0);
backtrack(board, i, board[0].size()-1);
}
for (int i = 1; i < board[0].size(); i++)
{
backtrack(board, 0, i);
backtrack(board, board.size()-1, i);
}
for (int i = 0; i < board.size(); i++)
{
for (int j = 0; j < board[0].size(); j++)
{
if (board[i][j] == NON_SURROUNDED) board[i][j] = 'O';
else board[i][j] = 'X';
}
}
}
void backtrack(vector<vector<char> > &board, int row, int col)
{
if (!isLegal(board, row, col)) return;
board[row][col] = NON_SURROUNDED;
backtrack(board, row+1, col);
backtrack(board, row-1, col);
backtrack(board, row, col+1);
backtrack(board, row, col-1);
}
bool isLegal(vector<vector<char> > &board, int i, int j)
{
return
!(i<0 || i>=board.size() || j<0 || j>=board[0].size() || board[i][j] != 'O');
}