Advertisement
Guest User

Untitled

a guest
Apr 30th, 2017
66
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.50 KB | None | 0 0
  1. #include <vector>
  2. #include <iostream>
  3.  
  4. using namespace std;
  5.  
  6. int n, m;
  7. vector<int> begin1;
  8.  
  9. vector<int> bfs() {
  10.     vector<int> d(n * m, -1);
  11.     for (int i = 0; i < begin1.size(); i++) {
  12.         d[begin1[i]] = 0;
  13.     }
  14.     vector<int> queue = begin1;
  15.     int qstart = 0;
  16.     while (qstart < queue.size()) {
  17.         int u = queue[qstart];
  18.         qstart++;
  19.         vector<int> go;
  20.         if (u % m != 0) {
  21.             go.push_back(u - 1);
  22.         }
  23.         if (u > m - 1) {
  24.             go.push_back(u - m);
  25.         }
  26.         if (u % m != m - 1) {
  27.             go.push_back(u + 1);
  28.         }
  29.         if (u < n * m - m) {
  30.             go.push_back(u + m);
  31.         }
  32.         for (int j = 0; j < go.size(); j++) {
  33.             int v = go[j];
  34.             if (d[v] == -1) {
  35.                 d[v] = d[u] + 1;
  36.                 queue.push_back(v);
  37.             }
  38.         }
  39.     }
  40.  
  41.     return d;
  42. }
  43.  
  44. int main() {
  45.     freopen("table.in", "r", stdin);
  46.     freopen("table.out", "w", stdout);
  47.     scanf("%d%d", &n, &m);
  48.     vector<int> table(n * m);
  49.     for (int i = 0; i < n; i++) {
  50.         for (int j = 0; j < m; j++) {
  51.             scanf("%d", &table[i * m + j]);
  52.             if (table[i * m + j] == 1) {
  53.                 begin1.push_back(i * m + j);
  54.             }
  55.         }
  56.     }
  57.     vector<int> lokoroko = bfs();
  58.     for (int i = 0; i < n; i++) {
  59.         for (int j = 0; j < m; j++) {
  60.             cout << lokoroko[i * m + j] << ' ';
  61.         }
  62.         cout << '\n';
  63.     }
  64.     return 0;
  65. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement