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 Xs思路： 1. 这种二维的题，套路就是用dfs。 2. 仔细观察和分辨，o有两种位置，一种是被包围的，一种是不被包围的，不被包围的就一定在四个边沿上可以看见。 3. 处理这两个位置，有两种思路：一种就是直接把被包围的找出来，然后替换成x；另一种，则反其道而行。不直接找被包围的，相对于被包围的，没有被包围的更容易找到，就在四边，通过遍历四条边沿，把和这些边连接的o找到，先暂时换成s，然后遍历一遍全部的符号，把o换成x，最后再遍历一遍，把s换回o即可！ 4. 哪个方法好？哪个快呢？先看第一个思路：在某个位置发现一个o,然后用dfs找相邻的o,这时候是还不知道这一块能不能被x全包围，就这么找，等相邻的区域全遍历过，发现能全包围，再遍历一遍把这些o给修改成o，很麻烦；而第二个思路中，就没有这样的问题，因为我们事先已经知道这些o是不被包围的，所以遍历的同时就修改成s，多省事！所以这个问题还是在边界处思考，求得解答！很多题的妙解都是在基于对边界的考虑，因为在边界处的行为是清楚的！ 5. 你看，看问题把两个方便都摆出来，比较比较，每个思路都想想，掂量掂量，也就差不多能看清问题的要害了! 6. 还可以用union find?
class Solution {public: void helper(vector<vector<char>>& board,vector<vector<int>>&dir,int i,int j){ ///* if(i<0||i>=board.size()||j<0||j>=board[0].size()||board[i][j]!='O') return; board[i][j]='S'; for(int k=0;k<4;k++){ helper(board,dir,i+dir[k][0],j+dir[k][1]); }*/ //bug:参考解释https://discuss.leetcode.com/topic/29091/why-this-code-has-runtime-error/3 //上面的解法导致stackoverflow!! if(board[i][j]=='O'){ board[i][j]='S'; if(i>1) helper(board,dir,i-1,j); if(i<board.size()-1) helper(board,dir,i+1,j); if(j>1) helper(board,dir,i,j-1); if(j<board[0].size()-1) helper(board,dir,i,j+1); } } void solve(vector<vector<char>>& board) { // int m=board.size(); if(m<2) return; int n=board[0].size(); if(n<2) return; vector<vector<int>> dir={{1,0},{-1,0},{0,1},{0,-1}}; for(int j=0;j<n;j+=(n-1)){//bug:n做了操作，需要保证n-1>=1，否则for循环就是死循环 for(int i=0;i<m;i++){ //if(board[i][j]=='O') helper(board,dir,i,j); } } for(int i=0;i<m;i+=(m-1)){ for(int j=0;j<n;j++){ //if(board[i][j]=='O') helper(board,dir,i,j); } } for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(board[i][j]=='O') board[i][j]='X'; else if(board[i][j]=='S') board[i][j]='O'; } } }};新闻热点
疑难解答
