Cannot pass due to time limit, but already changed to queue


  • 0
    X

    Hi, can anyone help me take a look at my solution? I already changed from recursive to iterative, but still cannot pass due to time limit. How can I further improve it?

    Thanks in advance!

    class Solution { 
    public:
        struct Node {
            int x, y;
            Node(int x_, int y_) : x(x_), y(y_) {}
        };
    
    void mark(vector<vector<char> > &board, Node cur) {
        if (board[cur.x][cur.y] == 'X' || board[cur.x][cur.y] == '+') { return; }
        
        queue<Node> q;
        q.push(cur);
        
        while (!q.empty()) {
            Node tmp = q.front(); q.pop();
            board[tmp.x][tmp.y] = '+';
            
            if (tmp.x > 0 && board[tmp.x-1][tmp.y] == 'O') { q.push(Node(tmp.x-1, tmp.y)); }
            if (tmp.y > 0 && board[tmp.x][tmp.y-1] == 'O') { q.push(Node(tmp.x, tmp.y-1)); }
            if (tmp.x < board.size()-1 && board[tmp.x+1][tmp.y] == 'O') { q.push(Node(tmp.x+1, tmp.y)); }
            if (tmp.y < board[0].size()-1 && board[tmp.x][tmp.y+1] == 'O') { q.push(Node(tmp.x, tmp.y+1)); }
        }
    }
    
    void solve(vector<vector<char> > &board) {
        if (board.size() == 0 || board[0].size() == 0) { return; }
        int m = board.size(), n = board[0].size();
        
        for (int i = 0; i < m; ++i) {
            if (board[i][0] == 'O') { mark(board, Node(i, 0)); }
            if (board[i][n-1] == 'O') { mark(board, Node(i, n-1)); }
        }
        
        for (int j = 1; j < n-1; ++j) {
            if (board[0][j] == 'O') { mark(board, Node(0, j)); }
            if (board[m-1][j] == 'O') { mark(board, Node(m-1, j)); }
        }
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j)
                if (board[i][j] == '+') { board[i][j] = 'O'; }
                else if (board[i][j] == 'O') { board[i][j] = 'X'; }
        }
    }
    

    };


  • 3
    S
            board[tmp.x][tmp.y] = '+';
    

    By setting board[tmp.x][tmp.y]='+' after you have popped it out of the queue, you are leaving a lot of scope of repeated entries.
    You should set this value to '+' while you are pushing it into your queue.


  • 0
    D

    Yes, you are right. I made the same mistake and can't find why I got TLE when use BFS.


Log in to reply
 

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