fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Function to calculate the minimum time required to infect all healthy cells
  5. int minTime(vector<vector<int>> ar) {
  6.     int n = ar.size();
  7.     int m = ar[0].size();
  8.  
  9.     queue<pair<int, int>> q;
  10.     int healthy = 0;      // count of healthy cells
  11.     int time = 0;
  12.  
  13.     // Initialize queue with all infected cells
  14.     for (int i = 0; i < n; i++) {
  15.         for (int j = 0; j < m; j++) {
  16.             if (ar[i][j] == 2) q.push({i, j});
  17.             else if (ar[i][j] == 1) healthy++;
  18.         }
  19.     }
  20.  
  21.     // Directions: up, down, left, right
  22.     int dx[] = {-1, 1, 0, 0};
  23.     int dy[] = {0, 0, -1, 1};
  24.  
  25.     // BFS traversal
  26.     while (!q.empty() && healthy > 0) {
  27.         int size = q.size();
  28.         while (size--) {
  29.             auto [x, y] = q.front();
  30.             q.pop();
  31.  
  32.             for (int d = 0; d < 4; d++) {
  33.                 int nx = x + dx[d];
  34.                 int ny = y + dy[d];
  35.  
  36.                 if (nx >= 0 && ny >= 0 && nx < n && ny < m && ar[nx][ny] == 1) {
  37.                     ar[nx][ny] = 2; // infect the healthy cell
  38.                     healthy--;
  39.                     q.push({nx, ny});
  40.                 }
  41.             }
  42.         }
  43.         time++; // one second passes after processing each level
  44.     }
  45.  
  46.     // If some healthy cells are still left, return -1
  47.     return (healthy == 0) ? time : -1;
  48. }
  49.  
  50. int main() {
  51.     ios::sync_with_stdio(false);
  52.     cin.tie(nullptr);
  53.  
  54.     int N, M;
  55.     cin >> N >> M;
  56.     vector<vector<int>> grid(N, vector<int>(M));
  57.  
  58.     for (int i = 0; i < N; i++) {
  59.         for (int j = 0; j < M; j++) {
  60.             cin >> grid[i][j];
  61.         }
  62.     }
  63.  
  64.     cout << minTime(grid) << "\n";
  65.     return 0;
  66. }
  67.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
2
3
2 0 1
1 1 0
stdout
copy 
-1
https://ideone.com/ZZXKd7
language:
C++ (gcc 8.3)
created:
12 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!