LeetCode(130) Surrounded Regions

タイトル
Given a 2D board containing  'X'  and  'O'  (the letter 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」に変えられず、残りの位置の「O」は「X」に変更される.したがって、各行の左右の境界、各列の上下の境界から順に要素を検査し、「O」から「X」に変更できない位置に対して「1」とマークする.
コード#コード#

class Solution {
public:
	void solve(vector>& board) {
		if (board.empty())
		{
			return;
		}

		int m = board.size(), n = board[0].size();
		/*    ，        O*/
		for (int i = 0; i < m; ++i)
		{
			//         
			check(board, i, 0, m, n);
			//     ，             
			if (n > 1)
				check(board, i, n - 1, m, n);
		}

		for (int j = 1; j < n-1; ++j)
		{
			//         
			check(board, 0, j, m, n);

			//     ，          
			if (m > 1)
				check(board, m - 1, j, m, n);
		}

		for (int i = 0; i < m; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				if (board[i][j] == 'O')
					board[i][j] = 'X';
			}//for
		}//for

		for (int i = 0; i < m; ++i)
		{
			for (int j = 0; j < n; ++j)
			{
				if (board[i][j] == '1')
					board[i][j] = 'O';
			}//for
		}//for
		
	}

	/*  （i,j）     'o',  'o'，   '1' */
	void check(vector>& board,int i, int j, int row, int col)
	{
		if (i < 0 || i >= row || j < 0 || j >= col)
			return;

		if (board[i][j] == 'O')
		{
			board[i][j] = '1';
			if (i > 1)
				check(board, i - 1, j, row, col);
			
			if (i < row - 1)
				check(board, i + 1, j, row, col);

			if (j > 1)
				check(board, i, j - 1, row, col);

			if (j < col - 1)
				check(board, i, j + 1, row, col);
		}
	}
};

GitHubソース