Advertisement
Josif_tepe

Untitled

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