24ms C++ solution


  • 0
    S

    Thanks for https://leetcode.com/discuss/74453/36-ms-c-solution

    Here is the modified version, with dist matrix eliminated;

    int shortestDistance(vector<vector<int>> grid) {
        int m = grid.size(), n = grid[0].size();
        auto total = grid;
        int walk = 0, mindist = INT_MAX, delta[] = {0, 1, 0, -1, 0};
        int buildings = 0;
        for (int i=0; i<m; ++i) {
            for (int j=0; j<n; ++j) {
                if (grid[i][j] == 2) {
                    total[i][j] = INT_MAX;
                }
                if (grid[i][j] == 1) {
                    int cur_dist = 1;
                    buildings++;
                    total[i][j] = INT_MAX;
                    vector<pair<int, int>> q;
                    q.emplace_back(i, j);
                    while (q.size()) {
                        vector<pair<int, int>> next_q;
                        for (auto ij: q) {
                            for (int d = 0; d < 4; ++d) {
                                int i = ij.first + delta[d];
                                int j = ij.second + delta[d+1];
                                if (i >= 0 && i < m && j >= 0 && j < n && grid[i][j] == walk) {
                                    grid[i][j]--;
                                    total[i][j] += cur_dist;
                                    next_q.emplace_back(i, j);
                                }
                            }
                        }
                        q.swap(next_q);
                        cur_dist++;
                    }
                    walk--;
                }
            }
        }
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (buildings + grid[i][j] == 0)
                    mindist = min(mindist, total[i][j]);
            }
        }
        return mindist == INT_MAX ? -1 : mindist;
    }

Log in to reply
 

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