本文共 1312 字，大约阅读时间需要 4 分钟。

这个问题有那么点感觉，但是就是不对路，开始想的是从左上角到右下角，若其左和上都是‘X'就将其改为’X‘，然后再从右下往上反，将“误杀”的还原回来，当然这要借助复制的一份board，但最终结果还是不对，因为有出现“弯路”的时候就不行了，后来想着再从右上到左下也如此操作一番，最终是没能得逞。几天无果，看了下discuss区，顿感醍醐灌顶，再看这个题，就 是呵呵。

思路是从外围是’O'的开始深度往里走，这时候里面的‘O'就有两种命运，一种是跟外围的’O'是联通的，那么这些‘O'就可以存活，剩下的孤立的’O'就没办法了，就只能被‘X'了，为了区分这两种’O'，我们把联通 的‘O'改为另外一种统一而独立的字符，便于后期做恢复。这就是三步走（或两步）。

1）首先从外围的‘O'处深度搜索，见到链接的’O'就把他们都改为其他标识。

2）将剩余的孤立的’O'改为‘X'，同时，将遇到标识符改为’O'。

简单吧，简单的一塌糊涂，但是这种思路太精髓了。

详细参考见：

class Solution {private:	int rows;	int cols;public:	void dfs(int row, int col,vector
   
    
      >& board)	{		if(row < 0 || row >= rows || col < 0 || col >= cols) return;		if(board[row][col] != 'O') return;		board[row][col] = '+';		dfs(row - 1, col, board);//up		dfs(row, col + 1, board);//right		dfs(row + 1, col, board);//down		dfs(row, col - 1, board);//left	}	void solve(vector
     
      
        > &board)	{		if(board.size() == 0 || board[0].size() == 0)			return;		 rows = board.size();		 cols = board[0].size();		 for(int i = 0; i < rows; ++i){			 dfs(i, 0, board);			 dfs(i, cols - 1, board);		 }		 for (int j = 0; j < cols; ++j)		 {			 dfs(0, j, board);			 dfs(rows - 1, j, board);		 }		 for(int i = 0; i < rows; ++i)			 for (int j = 0; j < cols; ++j)			 {				if(board[i][j] == 'O')					board[i][j] = 'X';				else if(board[i][j] == '+')					 board[i][j] = 'O';		 			 }	 	}};
      
     
    
   

转载地址：http://zrlji.baihongyu.com/