16ms C++ solution with BFS


  • 0
    D

    I improve the StefanPochmann code by computing the distances using one variable instead of a copy of grid.

    int shortestDistance(vector<vector<int>>& grid) {
        if (grid.empty())
            return -1;
        int m = grid.size(), n = grid.front().size(), reached = 0, global_min = 0;
        auto total_dists(grid);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    if (global_min == -1)return -1;
                    global_min = -1;
                    queue<pair<int, int>> q;
                    q.emplace(i, j);
                    int dist = 1, nnsl = 1; // num-nodes-same-level
                    const int ns = 4;
                    const array<pair<int, int>, ns> shifts{{{-1,0}, {1, 0}, {0, -1}, {0,1}}};
                    while (!q.empty()) {
                        auto cur = q.front();
                        q.pop();
                        int cx = cur.first, cy = cur.second;
                     
                        for (int k = 0; k < ns; ++k) {
                            int ax = cur.first + shifts[k].first, ay = cur.second + shifts[k].second;
                            if (ax >= 0 && ay >= 0 && ax <m && ay < n && grid[ax][ay] == reached) {
                                total_dists[ax][ay] += dist;
                                --grid[ax][ay];
                                if (total_dists[ax][ay] < global_min || global_min == -1)
                                    global_min = total_dists[ax][ay];
                                q.emplace(ax, ay);
                            }    
                        }
                        
                        if (--nnsl == 0) {
                            ++dist;
                            nnsl = q.size();
                        }
                    }
                    --reached;
                }
            }
        }
        return global_min;
    }
    

Log in to reply
 

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