Why my solution is Time Limit Exceeded


  • 0
    K

    I use BFS instead of DFS but still get TLE

    void Solution::markSurround(vector<vector<char>> &board, int i, int j, int row, int col)
    {
        board[i][j] = '#';
        queue<int> bfs;
        bfs.push(i * col + j);
    
        while (!bfs.empty())
        {
            int index = bfs.front();
            bfs.pop();
            int m = index / col;
            int n = index % col;
            board[m][n] = '#';
            if (m > 0 && board[m - 1][n] == 'O')
            {
                bfs.push((m - 1) * col + n);
            }
            if (m < row - 1 && board[m + 1][n] == 'O')
            {
                bfs.push((m + 1) * col + n);
            }
            if (n > 0 && board[m][n - 1] == 'O')
            {
                bfs.push(m * col + n - 1);
            }
            if (n < col - 1 && board[m][n + 1] == 'O')
            {
                bfs.push(m * col + n + 1);
            }
        }
    }
    
    void Solution::solve(vector<vector<char>> &board) {
        int row = board.size();
        if (row < 3)
        {
            return;
        }
        int col = board[0].size();
        for (int j = 0; j < col; j++)
        {
            if (board[0][j] == 'O')
            {
                markSurround(board, 0, j, row, col);
            }
            if (board[row - 1][j] == 'O')
            {
                markSurround(board, row - 1, j, row, col);
            }
        }
        for (int i = 0; i < row; i++)
        {
            if (board[i][0] == 'O')
            {
                markSurround(board, i, 0, row, col);
            }
            if (board[i][col - 1] == 'O')
            {
                markSurround(board, i, col - 1, row, col);
            }
        }
    
        for (int i = 0; i < row; i++)
        {
            for (int j = 0; j < col; j++)
            {
                if (board[i][j] == '#')
                {
                    board[i][j] = 'O';
                }
                else
                {
                    board[i][j] = 'X';
                }
            }
        }
    }

  • 3
    S

    In your bfs solution, you did board[m][n] = '#'; when get it from your bfs queue. However, it should be done when this position append to this queue, or there will be large duplicated elements in it.


Log in to reply
 

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