leecode 解题总结：130. Surrounded Regions

#include <iostream>#include <stdio.h>#include <vector>#include <string>#include <queue>using namespace std;/*问题: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 XX O O XX X O XX O X XAfter running your function, the board should be:X X X XX X X XX X X XX O X X输入:4(行) 4(列)X X X XX O O XX X O XX O X X输出:X X X XX X X XX X X XX O X X关键1 分析:此题实际上找到四周都是"X"的"O"，并把这些"O"替换为"X"。参考这位作者的解法:http://www.cnblogs.com/ganganloveu/p/3755191.html关键就是从何处开始替换。观察发现在边界上的"O"都不会被替换，先将这部分"O"转换为"#"，对于最后不是"#"的"O"就全部设置为"X"，然后再把"#"设置为"O"即可后续的遍历中会对边界的邻居结点上的"O"继续递归操作*/struct MyPoint{	MyPoint(int row , int col):_row(row),_col(col){}	MyPoint(){}	int _row;	int _col;};class Solution {public:	//对位置(curRow,curCol)即处于边界的元素上的"O"尝试都设置为"#"	void bfs(int curRow , int curCol , int row , int col,vector<vector<char>>& board)	{		if(curRow < 0 || curRow >= row || curCol < 0 || curCol >= col)		{			return;		}		//易错，当前元素要设置为"#"		board.at(curRow).at(curCol) = '#';		queue<MyPoint> points;		points.push(MyPoint(curRow , curCol));		MyPoint point;		while(!points.empty())		{			point = points.front();			points.pop();			//向下寻找"O"的元素			if( (point._row + 1) < row && 'O' == board.at( point._row + 1 ).at(point._col))			{				board.at( point._row + 1 ).at(point._col) = '#';				points.push(MyPoint(point._row + 1, point._col));			}						//向上			if( (point._row - 1) >= 0 && 'O' == board.at( point._row - 1 ).at(point._col) )			{				board.at(point._row - 1).at(point._col) = '#';				points.push(MyPoint(point._row - 1 , point._col));			}			//向右			if( (point._col + 1) < col && 'O' == board.at( point._row ).at(point._col + 1) )			{				board.at( point._row ).at(point._col + 1) = '#';				points.push(MyPoint( point._row , point._col + 1));			}			//向左			if( (point._col - 1) >= 0 && 'O' == board.at( point._row ).at(point._col - 1) )			{				board.at( point._row ).at(point._col - 1) = '#';				points.push(MyPoint( point._row , point._col - 1));			}		}	}    void solve(vector<vector<char>>& board) {        if(board.empty())		{			return;		}		int row = board.size();		int col = board.at(0).size();		//寻找四个边界上的"O"，然后递归修改为"#"		for(int i = 0 ; i < row ; i++)		{			for(int j = 0 ; j < col ; j++)			{				if(0 == i || row - 1 == i || 0 == j || col - 1 == j)				{					if('O' == board.at(i).at(j))					{						bfs(i , j , row , col , board);					}				}			}		}		//将"#"字符替换回原来的"O"		for(int i = 0 ; i < row ; i++)		{			for(int j = 0 ; j < col ; j++)			{				if('#' == board.at(i).at(j))				{					board.at(i).at(j) = 'O';				}				//凡是不是"#"的"O"，都是被围住的，全部修改为"X"				else if('O' == board.at(i).at(j))				{					board.at(i).at(j) = 'X';				}			}		}    }};void PRint(vector< vector<char> > result){	if(result.empty())	{		cout << "no result" << endl;		return;	}	int size = result.size();	int len = result.at(0).size();	for(int i = 0 ; i < size ; i++)	{		for(int j = 0 ; j < len; j++)		{			cout << result.at(i).at(j) << " " ;		}		cout << endl;	}}void process(){	 vector< vector<char> > board;	 char value;	 Solution solution;	 int row;	 int col;	 while(cin >> row >> col )	 {		 board.clear();		 for(int i = 0 ; i < row ; i++)		 {			 vector<char> nums;			 for(int j = 0 ; j < col ; j++)			 {				 cin >> value;				 nums.push_back(value);			 }			 board.push_back(nums);		 }		 solution.solve(board);		 print(board);	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}