Advertisement
mfgnik

Untitled

Nov 25th, 2020
476
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.41 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <utility>
  4.  
  5. int const inf = int(1e9 + 7);
  6.  
  7.  
  8. bool IsOk(int x, int y, int n, int m) {
  9.     return 0 <= x && x < n && 0 <= y && y < m;
  10. }
  11.  
  12.  
  13.  
  14. int main() {
  15.     int n, m;
  16.     std::cin >> n >> m;
  17.     std::vector<std::vector<int>>table(n, std::vector<int> (m));
  18.     std::vector<std::vector<int>>results(n, std::vector<int> (m));
  19.     std::queue<std::pair<int, int>> queue;
  20.     for (int i = 0; i < n; i++) {
  21.         for (int j = 0; j < m; j++) {
  22.             std::cin >> table[i][j];
  23.             results[i][j] = table[i][j] ? 0 : inf;
  24.             if (table[i][j])  {
  25.                 queue.emplace(i, j);
  26.             }
  27.         }
  28.     }
  29.  
  30.     while (!queue.empty()) {
  31.         auto [x, y] = queue.front();
  32.         queue.pop();
  33.         for (int i = -1; i <= 1; i++)
  34.             for (int j = -1; j <= 1; j++) {
  35.                 if (abs(i) + abs(j) != 1) {
  36.                     continue;
  37.                 }
  38.                 if (IsOk(x + i, y + j, n, m)) {
  39.                     if (results[x + i][y + j] > results[x][y] + 1) {
  40.                         results[x + i][y + j] = results[x][y] + 1;
  41.                         queue.emplace(x + i, y + j);
  42.                     }
  43.                 }
  44.             }
  45.     }
  46.    
  47.     for (int i = 0; i < n; i++) {
  48.         for (int j = 0; j < m; j++) {
  49.             std::cout << results[i][j] << " ";
  50.         }
  51.         std::cout << "\n";
  52.     }
  53.  
  54. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement