Leetcode Surrounded Regions

Surrounded Regions  
Total Accepted: 4258 
Total Submissions: 30340 My 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に置くことができます;
この特徴を把握していないので、難易度は5つ星です.
この特徴を知って、難易度は瞬間的に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');
	}