Advertisement
Josif_tepe

Untitled

Nov 7th, 2021
157
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.71 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3.  
  4. using namespace std;
  5. bool visited[1005][1005];
  6. int main()
  7. {
  8.     int a,b;
  9.     cin>>a>>b;
  10.     int n;
  11.     cin>>n;
  12.     int s;
  13.     cin>>s;
  14.     int x,y;
  15.     vector<pair<int,int>>v;
  16.     for(int i=0;i<a;i++)
  17.     {
  18.         for(int j=0;j<b;j++)
  19.         {
  20.             visited[i][j]=false;
  21.         }
  22.     }
  23.     for(int i=0;i<s;i++)
  24.     {
  25.         cin>>x>>y;
  26.         x--;
  27.         y--;
  28.         v.push_back(make_pair(x,y));
  29.         visited[x][y]=1;
  30.     }
  31.     queue<vector<pair<int,int>>>Q;
  32.     Q.push(v);
  33.     int kolkuM=0;
  34.     int kolkuZ=0;
  35.     while(!Q.empty())
  36.     {
  37.         vector<pair<int,int>>p=Q.front();
  38.         Q.pop();
  39.         vector<pair<int,int>>p2;
  40.         kolkuZ+=p.size();
  41.         if(kolkuZ>=n)
  42.         {
  43.             cout<<kolkuM;
  44.             return 0;
  45.         }
  46.         kolkuM++;
  47.         for(int i=0;i<p.size();i++)
  48.         {
  49.             int ci=p[i].first;
  50.             int cj=p[i].second;
  51.             if(ci+1<a && visited[ci+1][cj]==false)
  52.             {
  53.                 p2.push_back(make_pair(ci+1,cj));
  54.                 visited[ci+1][cj]=1;
  55.             }
  56.             if(ci-1>=0 && visited[ci-1][cj]==false)
  57.             {
  58.                 p2.push_back(make_pair(ci-1,cj));
  59.                 visited[ci-1][cj]=1;
  60.             }
  61.             if(cj+1<b && visited[ci][cj+1]==0)
  62.             {
  63.                 p2.push_back(make_pair(ci,cj+1));
  64.                 visited[ci][cj+1]=1;
  65.             }
  66.             if(cj-1>=0 && visited[ci][cj-1]==0)
  67.             {
  68.                 p2.push_back(make_pair(ci,cj-1));
  69.                 visited[ci][cj-1]=1;
  70.             }
  71.         }
  72.         Q.push(p2);
  73.     }
  74.     return 0;
  75. }
  76.  
  77. /*
  78.  ??XXX
  79.  ?XXXX
  80.  ??X??
  81.  
  82.  
  83.  **/
  84.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement