Hotel Service

• Time : $O(nm)$
• Space : $O(nm)$

vector<int> Solution::nearestHotel(vector<vector<int>> &A, vector<vector<int>> &B) {
    int n = A.size(), m = A[0].size();
    vector<vector<int>> mp(n, vector<int>(m,INT_MAX));
    queue<pair<int, int>> q;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(A[i][j]) {
                q.push({i,j});
                mp[i][j] = 0;
            }
        }
    }
    int dy[4]{-1,0,1,0}, dx[4]{0,1,0,-1};
    while(q.size()) {
        auto [y,x] = q.front(); q.pop();
        for(int i = 0; i < 4; i++) {
            int ny = y + dy[i], nx = x + dx[i];
            if(0 <= ny and ny < n and 0 <= nx and nx < m and mp[ny][nx] == INT_MAX) {
                mp[ny][nx] = mp[y][x] + 1;
                q.push({ny,nx});
            }
        }
    }
    vector<int> res;
    for(auto b : B) {
        res.push_back(mp[b[0]-1][b[1]-1]);
    }
    return res;
}