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 XX O O XX X O XX O X X

 

After running your function, the board should be:

X X X XX X X XX X X XX O X X

Method1: O(row*col*min(row,col))

1、把所有边上的不能被X包围的O换成P---O(row*col*min(row,col))，先从走上角开始换，再从右下角开始换，有的时候里面的O其实是和边上的O连通的，但是因为拐弯一次替换不能完成所以就要至少min(row,col)次替换。如果这个弯拐点太大了，这就完蛋了。。。能过Judge Large纯属幸运。。。

2、把里面的被X包围的O换成X---O(row*col)

3、把P换回O---O(row*col)

 

void solve(vector
    
     
      > &board) {    // Start typing your C/C++ solution below    // DO NOT write int main() function    int row = board.size();    if (row == 0) return;    int col = board[0].size();    if (col == 0) return;    //from left top to right down    for (int j = 0; j < col; ++j)        if (board[0][j] == 'O') board[0][j] = 'P';    for (int i = 0; i < row; ++i)        if (board[i][0] == 'O') board[i][0] = 'P';    for (int i = 1; i < row; ++i)    {        for (int j = 1; j < col; ++j)        {            if ((board[i][j] == 'O') && (board[i][j-1] == 'P' || board[i-1][j] == 'P'))                board[i][j] = 'P';        }    }    //from right down to left top    for (int j = 0; j < col; ++j)        if (board[row-1][j] == 'O') board[row-1][j] = 'P';    for (int i = 0; i < row; ++i)        if (board[i][col-1] == 'O') board[i][col-1] = 'P';    for (int i = row-2; i >= 0; --i)    {        for (int j = col-2; j >= 0; --j)        {            if ((board[i][j] == 'O') && (board[i][j+1] == 'P' || board[i+1][j] == 'P'))                board[i][j] = 'P';        }    }    //ensure    int time = row < col ? row : col;    for (int k = 1; k < time; ++k) {        for (int i = 1; i < row; ++i)        {            for (int j = 1; j < col; ++j)            {                if (board[i][j] == 'O') {                    if (board[i][j-1] == 'P' || board[i-1][j] == 'P')                        board[i][j] = 'P';                    if (j+1 < col && board[i][j+1] =='P')                        board[i][j] = 'P';                    if (i+1 < row && board[i+1][j] =='P')                        board[i][j] = 'P';                }            }        }    }    //change O to X    for (int i = 1; i < row; ++i)    {        for (int j = 1; j < col; ++j)        {            if (board[i][j] == 'O')                board[i][j] = 'X';        }    }    //change P to O    for (int i = 0; i < row; ++i)    {        for (int j = 0; j < col; ++j)        {            if (board[i][j] == 'P')                board[i][j] = 'O';        }    }}
     
    

 

这种方法的缺憾主要在第一步，如果优化的话，就是从矩阵的边界开始找O，只要找到O就从这个O开始BFS搜索把其相邻的O换成P直到相邻的没有O为止。这样就不用这么多次数的O(n^2)了吧。

 

void changeotop(vector
    
     
      > &board, int i, int j){	board[i][j] = 'P';	int row = board.size();	int col = board[0].size();	if(i>0 && board[i-1][j] == 'O')		changeotop(board, i-1, j);	if(j>0 && board[i][j-1] == 'O')		changeotop(board, i, j-1);	if(i+1
      
       > &board) {        // Start typing your C/C++ solution below        // DO NOT write int main() function        int row = board.size();		if(row == 0) return;		int col = board[0].size();		if(col == 0) return;		for(int j = 0; j < col; ++j)			if(board[0][j] == 'O') 				changeotop(board,0,j);		for(int i = 0; i < row; ++i)			if(board[i][0] == 'O')				changeotop(board,i,0);		for(int j = 0; j < col; ++j)			if(board[row-1][j] == 'O')				changeotop(board,row-1,j);		for(int i = 0; i < row; ++i)			if(board[i][col-1] == 'O')				changeotop(board,i,col);		//change O to X		for(int i = 1; i < row; ++i)		{			for(int j = 1; j < col; ++j)			{				if(board[i][j] == 'O')					board[i][j] = 'X';			}		}		//change P to O		for(int i = 0; i < row; ++i)		{			for(int j = 0; j < col; ++j)			{				if(board[i][j] == 'P')					board[i][j] = 'O';			}		}    }