tips for BFS if TLE


  • 0
    S

    If you want to find the nearest distance directly for every cell using BFS, your time is O(m^2*n^2) which will result in TLE.

    The best method is to find all zero cells and put them in queue, for which their nearest distance is 0.
    and then BFS it's neighbours, whose nearest distance is 1,
    and then the next level neighbours.

    my code for ref, any suggestion will be appreciated:)

        inline bool valid(vector<vector<int>> &m, int i, int j) {
            return i >= 0 && i < m.size() && j >= 0 && j < m[0].size();
        }
    public:
        vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
            if (matrix.size() == 0 || matrix[0].size() == 0) return vector<vector<int>>();
            int m = matrix.size(), n = matrix[0].size();
            vector<vector<int>> ans(m, vector<int>(n, INT_MAX)), v(m, vector<int>(n, 0));
            queue<pair<int, int>> Q;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (matrix[i][j] == 0) {
                        Q.push({i, j});
                        v[i][j] = 1;
                    }
                }
            }
            int cur = 0;
            while (!Q.empty()) {
                int size = Q.size();
                while (size--) {
                    auto p = Q.front();
                    Q.pop();
                    int i = p.first, j = p.second;
                    ans[i][j] = cur;
                    if (valid(v, i + 1, j) && !v[i + 1][j]) {Q.push({i + 1, j}); v[i+1][j] = 1;}
                    if (valid(v, i - 1, j) && !v[i - 1][j]) {Q.push({i - 1, j}); v[i-1][j] = 1;}
                    if (valid(v, i, j + 1) && !v[i][j + 1]) {Q.push({i, j + 1}); v[i][j+1] = 1;}
                    if (valid(v, i, j - 1) && !v[i][j - 1]) {Q.push({i, j - 1}); v[i][j-1] = 1;}
                }
                cur++;
            }
            return ans;
        }
    

Log in to reply
 

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