Advertisement
Josif_tepe

Untitled

Mar 14th, 2021
98
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.37 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. using namespace std;
  5.  
  6. int main()
  7. {
  8.     ios_base::sync_with_stdio(false);
  9.     int w, l, n, b, s = 0;
  10.     cin >> w >> l >> n >> b;
  11.     bool visited[1001][1001];
  12.     for (int i = 0; i < w; i++) {
  13.         for (int j = 0; j < l; j++) {
  14.             visited[i][j] = false;
  15.         }
  16.     }
  17.     int di[] = { 1, -1, 0, 0 };
  18.     int dj[] = { 0, 0, 1, -1 };
  19.     queue<vector<pair<int, int>>> q;
  20.     vector<pair<int, int>> v;
  21.     for (int i = 0; i < b; i++) {
  22.         int a, b2;
  23.         cin >> a >> b2;
  24.         v.push_back(make_pair(a - 1, b2 - 1));
  25.         visited[a-1][b2-1] = true;
  26.     }
  27.     q.push(v);
  28.     int b2 = b;
  29.     while (!q.empty()) {
  30.         vector<pair<int, int>> k, v2;
  31.         k = q.front();
  32.         q.pop();
  33.         for (int i = 0; i < k.size(); i++) {
  34.             for (int j = 0; j < 4; j++) {
  35.                 int c, p;
  36.                 c = k[i].first + di[j];
  37.                 p = k[i].second + dj[j];
  38.                 if (c >= 0 and c < w and p >= 0 and p < l and !visited[c][p]) {
  39.                     visited[c][p] = true;
  40.                     v2.push_back(make_pair(c, p));
  41.                     b2++;
  42.                 }
  43.             }
  44.         }
  45.         q.push(v2);
  46.         s++;
  47.         if (b2 >= n) {
  48.             cout << s << endl;
  49.             return 0;
  50.         }
  51.  
  52.     }
  53.  
  54.  
  55.     return 0;
  56. }
  57.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement