A really simple and readable C++ solution,only cost 12ms


  • 135
    S
    • First, check the four border of the matrix. If there is a element is
      'O', alter it and all its neighbor 'O' elements to '1'.
    • Then ,alter all the 'O' to 'X'
    • At last,alter all the '1' to 'O'

    For example:

             X X X X           X X X X             X X X X
             X X O X  ->       X X O X    ->       X X X X
             X O X X           X 1 X X             X O X X
             X O X X           X 1 X X             X O X X
        
    
    class Solution {
    public:
    	void solve(vector<vector<char>>& board) {
            int i,j;
            int row=board.size();
            if(!row)
            	return;
            int col=board[0].size();
    
    		for(i=0;i<row;i++){
    			check(board,i,0,row,col);
    			if(col>1)
    				check(board,i,col-1,row,col);
    		}
    		for(j=1;j+1<col;j++){
    			check(board,0,j,row,col);
    			if(row>1)
    				check(board,row-1,j,row,col);
    		}
    		for(i=0;i<row;i++)
    			for(j=0;j<col;j++)
    				if(board[i][j]=='O')
    					board[i][j]='X';
    		for(i=0;i<row;i++)
    			for(j=0;j<col;j++)
    				if(board[i][j]=='1')
    					board[i][j]='O';
        }
    	void check(vector<vector<char> >&vec,int i,int j,int row,int col){
    		if(vec[i][j]=='O'){
    			vec[i][j]='1';
    			if(i>1)
    				check(vec,i-1,j,row,col);
    			if(j>1)
    				check(vec,i,j-1,row,col);
    			if(i+1<row)
    				check(vec,i+1,j,row,col);
    			if(j+1<col)
    				check(vec,i,j+1,row,col);
    		}
    	}
    };

  • 0
    F

    It's quite readable. Thanks for sharing!


  • 10
    W

    Quite readable code! Just a slight improvement: your last part can be replaced by the following:

    for (int i = 0; i < row; i++)
        for (int j = 0; j < col; j++)
            board[i][j] = (board[i][j] == '1') ? 'O' : 'X';

  • 0
    S

    OK,3Q for your comment~


  • 3
    K

    Dude, you are exposed by saying 3Q :-) @sugeladi


  • 0
    J

    This is actually a DFS solution


  • 0
    C

    I am really impressed by the thought. Straightforward and easy to understand:)


  • 116
    R

    This is a DFS solution, but it may causes a stack overflow issue.

    When you use DFS, it is tricky to use:

            if(i>1)
                check(vec,i-1,j,row,col);
            if(j>1)
                check(vec,i,j-1,row,col);
    

    because it is more common to write like this:

            if(i>=1)
                check(vec,i-1,j,row,col);
            if(j>=1)
                check(vec,i,j-1,row,col);
    

    Then I'll explain it.

    There is a test case like this:

    OOOOOOOOOO
    XXXXXXXXXO
    OOOOOOOOOO
    OXXXXXXXXX
    OOOOOOOOOO
    XXXXXXXXXO
    OOOOOOOOOO
    OXXXXXXXXX
    OOOOOOOOOO
    XXXXXXXXXO
    

    To make it clear, I draw a 10x10 board, but it is actually a 250x250 board like this one.

    When dfs function visit board[0][0], it ought to visit every grid marked 'O', thus lead to stack overflow(runtime error).

    After you change "if(j>=1)" to "if(j>1)", the DFS function won't check board[i][0] (0<=i<=row-1), and then not all the grids marked 'O' will be visited when you dfs(board[0][0]).
    Your code won't cause stack overflow in this test case, but if we change the test case a little, it won't work well.

    Consider a test case like this:

    OOOOOOOOOOOX
    XXXXXXXXXXOX
    XOOOOOOOOOOX
    XOXXXXXXXXXX
    XOOOOOOOOOOX
    XXXXXXXXXXOX
    XOOOOOOOOOOX
    XOXXXXXXXXXX
    XOOOOOOOOOOX
    XXXXXXXXXXOX
    

    I draw a 10x12 board, but it may be as large as the 250x250 board.

    I believe that your code will get "runtime error" in this test case when tested in Leetcode system.


  • 0
    S

    Thank you for your comment
    I didn't take my laptop with me. And I have read your comment carefully.
    I do not think it will bring a endless loop.
    I write the (i>1), and also write the (i+1<row), it means the search will end when the point is at the second last position.
    Also, a point is changed to '1',and not '0' at all, it prevent the repeated search I think.
    Because my solution only search begin with the bound points,so it is OK to end with the bound points.
    My English is not very well, I dont know if I have explain it clearly.


  • 4
    R

    Thank you for your reply.
    I am sure that your code won't bring an endless loop, because my code is really similar with yours.
    The only difference is that I use "if(i>=1)" & "if(j>=1)", while you use "if(i>1)" & "if(j>1)".
    As we have visited the bound grids, it is fine to avoid visiting them in DFS function.
    So I drew the test case that causes stack overflow and want to find out what happend in that test case.
    In the first test case that I drew, when I call dfs(board[0][0]) in main function, it ought to visit all the grids that marked "O".
    It is like a chain, and there are too many grids in this "chain" (the test case is 250x250). So it recurses too deeply and causes stack overflow.
    Your code won't cause stack overflow because you ignore the bound grids. As a result, you split the chain into several parts, and it will only visit one of these parts when you call DFS in main function. Then it won't recurses too deeply, and won't cause stack over flow.
    But when I change the test case a little, your code still faces the situation that visit all the grids marked "O" in one dfs() call in main function. In the second test case that I drew, the chain won't be splited into several parts.
    So what I want to say is that your code can get accepted just because the test cases haven't cover all properties, and we should use BFS to solve this problem.


  • 0
    S

    I am sure that there is no repeated search in my solution. It means every point is searched for only one time, why it cause the stack overflow. Please read my solution carefully. There may be something different with your code.


  • 2
    R

    It causes the stack overflow because it recurses too deeply, not repeating search. Your code won't get runtime error just because the test case is weak.


  • 0
    Y

    I came across the exact same issue. When I use (i>=1) instead of (i>1), I get runtime error. Thank @returnans to point it out.


  • 0
    T

    Same Idea, But BFS solution:

    void BFS(vector<vector<char>> &board, int x, int y){
        	int x_size(board.size()),y_size(board[0].size());
        	deque<pair<int, int> > bfsdeq;
        	bfsdeq.emplace_back(x,y);
        	board[x][y] = 'Q';
        	while(!bfsdeq.empty()){
        		pair<int, int> &curp = bfsdeq.front();
        		int i = curp.first;
    			int j = curp.second;
    			bfsdeq.pop_front();
    			if (i > 0 && 'O' == board[i - 1][j])
    			{
    				bfsdeq.emplace_back(i - 1, j);
    				board[i-1][j] = 'Q';
    			}
    			if (i + 1 <  x_size && 'O' == board[i + 1][j])
    			{
    				bfsdeq.emplace_back(i + 1, j);
    				board[i+1][j] = 'Q';
    			}
    			if (j > 0 && 'O' == board[i][j - 1])
    			{
    				bfsdeq.emplace_back(i, j-1);
    				board[i][j-1] = 'Q';
    			}
    			if (j + 1 <  y_size && 'O' == board[i][j +1])
    			{
    				bfsdeq.emplace_back(i,  j+1);
    				board[i][j+1] = 'Q';
    			}
    
    		}
    	}
    	void solve(vector<vector<char>> &board) {
    		if(board.size() < 3) return;
    		if (board[0].size() < 3) return;
    		int b_margin = board.size()-1;
    		for(int i = 0; i < board[0].size(); ++i){
    			if('O' == board[0][i]){
    				BFS(board, 0, i);
    			}
    			if('O' == board[b_margin][i]){
    				BFS(board, b_margin, i);
    			}
    		}
    
    		int r_margin = board[0].size()-1;
    		for (int i = 1; i < b_margin; ++i)
    		{
    
    			if('O' == board[i][0]){
    				BFS(board, i, 0);
    			}
    			if ('O' == board[i][r_margin])
    			{
    				BFS(board, i, r_margin);
    			}
    		}
    		for (int i = 0; i < board.size(); ++i)
    		{
    			for (int j = 0; j < board[i].size(); ++j)
    			{
    				switch(board[i][j]){
    				case 'Q':
    					board[i][j] = 'O';
    					break;
    				default:
    					board[i][j] = 'X';
    					break;
    				}
    
    			}
    		}
    	}

  • 0
    A

    if(i>1) should be if(i>=1) like @returnans pointed out, then you'll get Stack Overflow.


  • 0
    C

    Exactly, deep recursion may yield stack overflow.


  • 0

    Your solution is really good and easy to understand, Thank you.


  • 0
    S

    This solution is a DFS method.And the max depth of the recurses is the size of the matrix.So the max recurse depth of my solution test for the 250*250 size case is 250.


  • 0
    S

    This solution is a DFS method.And the max depth of the recurses is the size of the matrix.So the max recurse depth of my solution test for the 250*250 size case is 250.


  • -1
    S

    This solution is a DFS method.And the max depth of the recurses is the size of the matrix.So the max recurse depth of my solution test for the 250*250 size case is 250.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.