fork download
copy 
  1. /*
  2. QUESTION 10: Placing One More Delivery Hub
  3.  
  4. Problem Statement:
  5. You are given a binary grid.
  6.  
  7. 1 means there is already a delivery hub.
  8. 0 means the cell is empty.
  9.  
  10. You must place exactly one new hub on an empty cell.
  11.  
  12. Distance between cells is:
  13. max(abs(row1 - row2), abs(col1 - col2))
  14.  
  15. For every cell, inconvenience is the distance to the nearest hub.
  16.  
  17. Return the smallest possible maximum inconvenience after adding one hub.
  18.  
  19. Hard Constraints:
  20. 1 <= rows, cols
  21. rows * cols <= 200000
  22. At least one existing hub exists.
  23. At least one empty cell exists.
  24.  
  25. Example:
  26. grid =
  27. [
  28.   [1, 0],
  29.   [0, 0]
  30. ]
  31.  
  32. Expected Output:
  33. 1
  34.  
  35. Explanation:
  36. Place the new hub at the bottom-right cell.
  37. Every cell becomes within distance 1 from some hub.
  38.  
  39. Brute Force:
  40. Try every empty cell as the new hub.
  41. For each placement, compute nearest hub distance for every grid cell.
  42.  
  43. Time Complexity:
  44. O((rows * cols)^2)
  45.  
  46. Optimized Approach:
  47. First compute distance from every cell to nearest existing hub using multi-source BFS
  48. in 8 directions.
  49.  
  50. Then binary search answer D.
  51.  
  52. For every cell whose current distance is greater than D:
  53. the new hub must be within distance D from it.
  54.  
  55. Each such cell creates a rectangle of possible hub positions.
  56. Intersect all rectangles.
  57.  
  58. If the final intersection contains an empty cell, D is possible.
  59.  
  60. Time Complexity:
  61. O(rows * cols * log(max(rows, cols)))
  62.  
  63. Space Complexity:
  64. O(rows * cols)
  65. */
  66.  
  67. #include <bits/stdc++.h>
  68. using namespace std;
  69.  
  70. class Solution {
  71. public:
  72.     int minimumInconvenience(vector<vector<int>>& grid) {
  73.         int n = grid.size();
  74.         int m = grid[0].size();
  75.  
  76.         const int INF = 1e9;
  77.  
  78.         vector<vector<int>> dist(n, vector<int>(m, INF));
  79.         queue<pair<int, int>> q;
  80.  
  81.         for (int i = 0; i < n; i++) {
  82.             for (int j = 0; j < m; j++) {
  83.                 if (grid[i][j] == 1) {
  84.                     dist[i][j] = 0;
  85.                     q.push({i, j});
  86.                 }
  87.             }
  88.         }
  89.  
  90.         vector<pair<int, int>> dirs = {
  91.             {1, 0}, {-1, 0}, {0, 1}, {0, -1},
  92.             {1, 1}, {1, -1}, {-1, 1}, {-1, -1}
  93.         };
  94.  
  95.         while (!q.empty()) {
  96.             auto [x, y] = q.front();
  97.             q.pop();
  98.  
  99.             for (auto [dx, dy] : dirs) {
  100.                 int nx = x + dx;
  101.                 int ny = y + dy;
  102.  
  103.                 if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
  104.                     if (dist[nx][ny] > dist[x][y] + 1) {
  105.                         dist[nx][ny] = dist[x][y] + 1;
  106.                         q.push({nx, ny});
  107.                     }
  108.                 }
  109.             }
  110.         }
  111.  
  112.         vector<vector<int>> pref(n + 1, vector<int>(m + 1, 0));
  113.  
  114.         for (int i = 0; i < n; i++) {
  115.             for (int j = 0; j < m; j++) {
  116.                 pref[i + 1][j + 1] =
  117.                     pref[i][j + 1] +
  118.                     pref[i + 1][j] -
  119.                     pref[i][j] +
  120.                     (grid[i][j] == 0);
  121.             }
  122.         }
  123.  
  124.         auto emptyCount = [&](int x1, int y1, int x2, int y2) {
  125.             if (x1 > x2 || y1 > y2) return 0;
  126.  
  127.             return pref[x2 + 1][y2 + 1]
  128.                  - pref[x1][y2 + 1]
  129.                  - pref[x2 + 1][y1]
  130.                  + pref[x1][y1];
  131.         };
  132.  
  133.         auto can = [&](int D) {
  134.             int lx = 0, rx = n - 1;
  135.             int ly = 0, ry = m - 1;
  136.  
  137.             bool hasBad = false;
  138.  
  139.             for (int i = 0; i < n; i++) {
  140.                 for (int j = 0; j < m; j++) {
  141.                     if (dist[i][j] > D) {
  142.                         hasBad = true;
  143.  
  144.                         lx = max(lx, i - D);
  145.                         rx = min(rx, i + D);
  146.  
  147.                         ly = max(ly, j - D);
  148.                         ry = min(ry, j + D);
  149.                     }
  150.                 }
  151.             }
  152.  
  153.             if (!hasBad) return true;
  154.             if (lx > rx || ly > ry) return false;
  155.  
  156.             return emptyCount(lx, ly, rx, ry) > 0;
  157.         };
  158.  
  159.         int low = 0;
  160.         int high = max(n, m);
  161.         int ans = high;
  162.  
  163.         while (low <= high) {
  164.             int mid = low + (high - low) / 2;
  165.  
  166.             if (can(mid)) {
  167.                 ans = mid;
  168.                 high = mid - 1;
  169.             } else {
  170.                 low = mid + 1;
  171.             }
  172.         }
  173.  
  174.         return ans;
  175.     }
  176. };
  177.  
  178. int main() {
  179.     Solution sol;
  180.  
  181.     vector<vector<int>> grid = {
  182.         {1, 0},
  183.         {0, 0}
  184.     };
  185.  
  186.     cout << sol.minimumInconvenience(grid) << endl;
  187.  
  188.     return 0;
  189. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/W48n8r
language:
C++14 (gcc 8.3)
created:
9 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!