Advertisement
Josif_tepe

Untitled

Oct 20th, 2024
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.70 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4.  
  5. using namespace std;
  6.  
  7. const int dx[4]={1,0,-1,0};
  8. const int dj[4]={0,1,0,-1};
  9.  
  10. int main()
  11. {
  12.     int n,m,k;
  13.     cin>>n>>m;
  14.     cin>>k;
  15.     char x[n][m];
  16.     vector<pair<int,int>>v;
  17.     for(int i = 0;i<n;i++){
  18.         for(int j = 0;j<m;j++){
  19.             cin>>x[i][j];
  20.             if(x[i][j]=='C'){
  21.               v.push_back(make_pair(i,j));
  22.             }
  23.         }
  24.     }
  25.     int si;
  26.     int sj;
  27.     int cnt[n][m];
  28.     for(int i = 0;i<n;i++){
  29.         for(int j = 0;j<m;j++){
  30.             cnt[i][j]=0;
  31.         }
  32.     }
  33.     for(int i = 0;i<v.size();i++){
  34.         queue<int>q;
  35.         si=v[i].first;
  36.         sj=v[i].second;
  37.         q.push(si);
  38.         q.push(sj);
  39.         q.push(0);
  40.         vector<vector<bool>>visited(n,vector<bool>(m,false));
  41.         while(!q.empty()){
  42.           int ci=q.front();
  43.           q.pop();
  44.           int cj=q.front();
  45.           q.pop();
  46.           int dist=q.front();
  47.           q.pop();
  48.           for(int p = 0;p<4;p++){
  49.             int ti=ci+dx[p];
  50.             int tj=cj+dj[p];
  51.             if(ti>=0 && ti<n && tj>=0 && tj<m && x[ti][tj]!='#' && visited[ti][tj]==false && dist+1<=k){
  52.                 visited[ti][tj]=true;
  53.                 q.push(ti);
  54.                 q.push(tj);
  55.                 q.push(dist+1);
  56.                 cnt[ti][tj]++;
  57.             }
  58.           }
  59.        }
  60.     }
  61.     int najgolem=0;
  62.     int ri;
  63.     int rj;
  64.     for(int i = 0;i<n;i++){
  65.         for(int j = 0;j<m;j++){
  66.             if(cnt[i][j]>najgolem and x[i][j] != 'C'){
  67.                 najgolem=cnt[i][j];
  68.                 ri=i;
  69.                 rj=j;
  70.             }
  71.         }
  72.     }
  73.   cout<<ri + 1<<" "<<rj + 1<<endl;
  74. }
  75.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement