fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <algorithm>
  5.  
  6. class Solution {
  7. public:
  8.     // Helper to check if a valid intersection of coverage squares exists
  9.     bool check(int D, int n, int m, const std::vector<std::vector<int>>& initial_dist) {
  10.         // Find the required intersection bounds for the new delivery center.
  11.         int min_px_bound = 0, max_px_bound = n - 1;
  12.         int min_py_bound = 0, max_py_bound = m - 1;
  13.  
  14.         bool has_critical_points = false;
  15.  
  16.         // Find all critical points (q) and tighten the bounds for our new center (p).
  17.         for (int i = 0; i < n; ++i) {
  18.             for (int j = 0; j < m; ++j) {
  19.                 if (initial_dist[i][j] > D) {
  20.                     has_critical_points = true;
  21.                     // A new center at (px, py) must cover (i, j).
  22.                     // This means max(|px-i|, |py-j|) <= D, which implies:
  23.                     // i - D <= px <= i + D
  24.                     // j - D <= py <= j + D
  25.                     min_px_bound = std::max(min_px_bound, i - D);
  26.                     max_px_bound = std::min(max_px_bound, i + D);
  27.                     min_py_bound = std::max(min_py_bound, j - D);
  28.                     max_py_bound = std::min(max_py_bound, j + D);
  29.                 }
  30.             }
  31.         }
  32.  
  33.         if (!has_critical_points) {
  34.             return true; // No points need covering, so D is achievable.
  35.         }
  36.  
  37.         // If the intersection is valid, a point p exists that can cover all critical points.
  38.         return min_px_bound <= max_px_bound && min_py_bound <= max_py_bound;
  39.     }
  40.  
  41.     int getMinInconvenience(std::vector<std::vector<int>>& grid) {
  42.         int n = grid.size();
  43.         if (n == 0) return 0;
  44.         int m = grid[0].size();
  45.         if (m == 0) return 0;
  46.  
  47.         // Phase 1: Preprocessing - Calculate initial distances
  48.         std::vector<std::vector<int>> initial_dist(n, std::vector<int>(m, -1));
  49.         std::queue<std::pair<int, int>> q;
  50.         bool has_delivery_center = false;
  51.  
  52.         for (int i = 0; i < n; ++i) {
  53.             for (int j = 0; j < m; ++j) {
  54.                 if (grid[i][j] == 1) {
  55.                     q.push({i, j});
  56.                     initial_dist[i][j] = 0;
  57.                     has_delivery_center = true;
  58.                 }
  59.             }
  60.         }
  61.  
  62.         // If no delivery centers exist, we must place one.
  63.         // We can skip the BFS and go straight to binary search.
  64.         if (has_delivery_center) {
  65.             int dr[] = {-1, -1, -1, 0, 0, 1, 1, 1};
  66.             int dc[] = {-1, 0, 1, -1, 1, -1, 0, 1};
  67.             int head = 0;
  68.             while(!q.empty()){
  69.                 std::pair<int,int> curr = q.front();
  70.                 q.pop();
  71.  
  72.                 for(int i=0; i<8; ++i){
  73.                     int nr = curr.first + dr[i];
  74.                     int nc = curr.second + dc[i];
  75.  
  76.                     if(nr >= 0 && nr < n && nc >= 0 && nc < m && initial_dist[nr][nc] == -1){
  77.                         initial_dist[nr][nc] = initial_dist[curr.first][curr.second] + 1;
  78.                         q.push({nr, nc});
  79.                     }
  80.                 }
  81.             }
  82.         } else {
  83.              // If no centers, treat initial distances as infinite
  84.             for(int i = 0; i < n; ++i) {
  85.                 for(int j = 0; j < m; ++j) {
  86.                     initial_dist[i][j] = n + m; // A value larger than any possible distance
  87.                 }
  88.             }
  89.         }
  90.  
  91.         // Phase 2: Binary Search for the minimum possible inconvenience D
  92.         int low = 0, high = n + m, ans = n + m;
  93.  
  94.         while (low <= high) {
  95.             int mid = low + (high - low) / 2;
  96.             if (check(mid, n, m, initial_dist)) {
  97.                 // It's possible to achieve inconvenience 'mid'. Try for an even smaller one.
  98.                 ans = mid;
  99.                 high = mid - 1;
  100.             } else {
  101.                 // Not possible. We need to allow for a larger inconvenience.
  102.                 low = mid + 1;
  103.             }
  104.         }
  105.  
  106.         return ans;
  107.     }
  108. };
  109. // Example Usage
  110. int main() {
  111.     Solution sol;
  112.  
  113.     // Sample Case 0 from problem description
  114.     std::vector<std::vector<int>> grid1 = {
  115.         {0, 0, 0, 0},
  116.         {0, 0, 0, 0},
  117.         {0, 0, 0, 0}
  118.     };
  119.     std::cout << "Sample Case 0:" << std::endl;
  120.     std::cout << "Expected Output: 2" << std::endl;
  121.     std::cout << "Actual Output:   " << sol.getMinInconvenience(grid1) << std::endl;
  122.     std::cout << "---------------------" << std::endl;
  123.  
  124.  
  125.     // Sample Case 1 from problem description
  126.     std::vector<std::vector<int>> grid2 = {{0}};
  127.     std::cout << "Sample Case 1:" << std::endl;
  128.     std::cout << "Expected Output: 0" << std::endl;
  129.     std::cout << "Actual Output:   " << sol.getMinInconvenience(grid2) << std::endl;
  130.     std::cout << "---------------------" << std::endl;
  131.  
  132.     // First example from problem description
  133.     std::vector<std::vector<int>> grid3 = {
  134.         {0, 0, 0, 1},
  135.         {0, 0, 0, 1}
  136.     };
  137.     std::cout << "Problem Description Example:" << std::endl;
  138.     std::cout << "Expected Output: 1" << std::endl;
  139.     std::cout << "Actual Output:   " << sol.getMinInconvenience(grid3) << std::endl;
  140.     std::cout << "---------------------" << std::endl;
  141.  
  142.     return 0;
  143. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Sample Case 0:
Expected Output: 2
Actual Output:   2
---------------------
Sample Case 1:
Expected Output: 0
Actual Output:   0
---------------------
Problem Description Example:
Expected Output: 1
Actual Output:   1
---------------------
https://ideone.com/URbgSo
language:
C++14 (gcc 8.3)
created:
15 days 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!