Advertisement
Josif_tepe

Untitled

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