Share my CPP BFS solution~


  • 0
    O
    #define MP make_pair
    #define MT make_tuple
    class Solution {
    public:
        int shortestDistance(vector<vector<int>>& grid) {
            int N = grid.size();
            if (N <= 0) return 0;
            int M = grid[0].size();
            if (M <= 0) return 0;
            int checkcnt = 0;
            vector<vector<int> > dis(N, vector<int>(M, 0));
            vector<vector<int> > cnt(N, vector<int>(M, 0));
            int ans = INT_MAX;
            int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
            for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) {
                if (grid[i][j] == 1) {
                    checkcnt++;
                    queue<tuple<int, int, int> > Q;
                    map<pair<int, int>, bool> vis;
                    vis[MP(i, j)] = true;
                    Q.push(MT(i, j, 0));
                    while (!Q.empty()) {
                        int cx = get<0>(Q.front()), cy = get<1>(Q.front()), cs = get<2>(Q.front()); Q.pop();
                        for (int k = 0; k < 4; k++) {
                            int nx = cx + dx[k], ny = cy + dy[k];
                            if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
                            if (vis[MP(nx, ny)]) continue;
                            if (grid[nx][ny] != 0) continue;
                            vis[MP(nx, ny)] = true;
                            cnt[nx][ny]++;
                            Q.push(MT(nx, ny, cs + 1));
                            dis[nx][ny] += cs + 1;
                        }
                    }
                }
            }
            for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) if (grid[i][j] == 0 && cnt[i][j] == checkcnt) {
                ans = min(ans, dis[i][j]);
            }
            return (ans == INT_MAX ? -1 : ans);
        }
    };

Log in to reply
 

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