#include <iostream>#include <stdio.h>#include <vector>#include <string>#include <queue>using namespace std;/*問(wèn)題: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關(guān)鍵1 分析:此題實(shí)際上找到四周都是"X"的"O"，并把這些"O"替換為"X"。參考這位作者的解法:http://www.cnblogs.com/ganganloveu/p/3755191.html關(guān)鍵就是從何處開始替換。觀察發(fā)現(xiàn)在邊界上的"O"都不會(huì)被替換，先將這部分"O"轉(zhuǎn)換為"#"，對(duì)于最后不是"#"的"O"就全部設(shè)置為"X"，然后再把"#"設(shè)置為"O"即可后續(xù)的遍歷中會(huì)對(duì)邊界的鄰居結(jié)點(diǎn)上的"O"繼續(xù)遞歸操作*/struct MyPoint{	MyPoint(int row , int col):_row(row),_col(col){}	MyPoint(){}	int _row;	int _col;};class Solution {public:	//對(duì)位置(curRow,curCol)即處于邊界的元素上的"O"嘗試都設(shè)置為"#"	void bfs(int curRow , int curCol , int row , int col,vector<vector<char>>& board)	{		if(curRow < 0 || curRow >= row || curCol < 0 || curCol >= col)		{			return;		}		//易錯(cuò)，當(dāng)前元素要設(shè)置為"#"		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();		//尋找四個(gè)邊界上的"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);					}				}			}		}		//將"#"字符替換回原來(lái)的"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;}