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'; } } }};新聞熱點
疑難解答
