Why my code is so slowly? Using DFS 40ms.


  • 0
    E
    class Solution {
    public:
    void solve(vector<vector<char>>& board)
    {
        if (board.size() == 0)
            return;
        if (board[0].size() == 0)
            return;
        	
    	std::vector<std::vector<bool>> visited(board.size(), std::vector<bool>(board[0].size(), false));
    	
    	// top
    	for (int i = 0; i < board[0].size(); ++i)
    		dfs(board, 0, i, visited, true);
    	// bottom
    	for (int i = 0; i < board[0].size(); ++i)
    		dfs(board, board.size() - 1, i, visited, true);
    	// left
    	for (int i = 0; i < board.size(); ++i)
    		dfs(board, i, 0, visited, true);
    	// right
    	for (int i = 0; i < board.size(); ++i)
    		dfs(board, i, board[0].size() - 1, visited, true);
    
    	// the rest point
    	for (int i = 1; i < board.size() - 1; ++i)
    		for (int j = 1; j < board[i].size() - 1; ++j)
    		{
    		    if (!visited[i][j] && board[i][j] == 'O')
    		        board[i][j] = 'X';
    		}	
    }
    
    private:
    void dfs(std::vector<std::vector<char>> &board, int row, int col, std::vector<std::vector<bool>> &visited, bool isAtBounder)
    {
    	if (row < 0 || row >= board.size())
    		return;
    	if (col < 0 || col >= board[row].size())
    		return;
    	if (visited[row][col])
    		return;
    
    	stack<pair<int, int>> stk;
    	stk.push(make_pair(row, col));
    	
    	while (!stk.empty())
    	{
    		pair<int, int> point = stk.top();
    		stk.pop();
    
    		int i = point.first;
    		int j = point.second;
    
    		if (visited[i][j])
    			continue;
    
    		visited[i][j] = true;
    		if (board[i][j] == 'O')
    		{
    			if (!isAtBounder)
    				board[i][j] = 'X';
    
                if (i - 1 >= 0 && i - 1 < board.size() && !visited[i - 1][j])
    			    stk.push(make_pair(i - 1, j));
    			if (i + 1 >= 0 && i + 1 < board.size() && !visited[i + 1][j])
    			    stk.push(make_pair(i + 1, j));
    			if (j - 1 >= 0 && j - 1 < board[row].size() && !visited[i][j - 1])
    			    stk.push(make_pair(i, j - 1));
    			if (j + 1 >= 0 && j + 1 < board[row].size() && !visited[i][j + 1])
    			    stk.push(make_pair(i, j + 1));
    		}	
    	}
    }
    };

Log in to reply
 

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