Advertisement
Josif_tepe

Untitled

Oct 30th, 2024
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.32 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4. using namespace std;
  5. const int maxn = 1005;
  6. char mat[maxn][maxn];
  7. int n, m;
  8.  
  9. int main() {
  10.     cin >> n >> m;
  11.     int W;
  12.     cin >> W;
  13.    
  14.     for(int i = 0; i < n; i++) {
  15.         for(int j = 0; j < m; j++) {
  16.             cin >> mat[i][j];
  17.            
  18.            
  19.         }
  20.     }
  21.     ;
  22.    
  23.     vector<vector<int>> cnt(n, vector<int>(m, 0));
  24.     int di[] = {-1, 1, 0, 0};
  25.     int dj[] = {0, 0, -1, 1};
  26.    
  27.     for(int i = 0; i < n; i++) {
  28.         for(int j = 0; j < m; j++) {
  29.             if(mat[i][j] == 'C') {
  30.                 vector<vector<bool>> visited(n, vector<bool>(m, false));
  31.                 int si = i;
  32.                 int sj = j;
  33.                 queue<int> q;
  34.                 q.push(si);
  35.                 q.push(sj);
  36.                 q.push(0);
  37.                 visited[si][sj] = true;
  38.                 while(!q.empty()) {
  39.                     int ci = q.front();
  40.                     q.pop();
  41.                     int cj = q.front();
  42.                     q.pop();
  43.                     int d = q.front();
  44.                     q.pop();
  45.                    
  46.                     if(d > W) {
  47.                         continue;
  48.                     }
  49.                     if(mat[ci][cj] == '.') {
  50.                         cnt[ci][cj]++;
  51.                     }
  52.                    
  53.                     for(int k = 0; k < 4; k++) {
  54.                         int ti = ci + di[k];
  55.                         int tj = cj + dj[k];
  56.                        
  57.                         if(ti >= 0 and ti < n and tj >= 0 and tj < m and !visited[ti][tj] and mat[ti][tj] != '#') {
  58.                             q.push(ti);
  59.                             q.push(tj);
  60.                             q.push(d + 1);
  61.                             visited[ti][tj] = true;
  62.                         }
  63.                     }
  64.                 }
  65.                
  66.             }
  67.         }
  68.     }
  69.    
  70.     int res = 0, ei, ej;
  71.     for(int i = 0; i < n; i++) {
  72.         for(int j = 0; j < m; j++) {
  73.             if(mat[i][j] == '.') {
  74.                 if(res < cnt[i][j]) {
  75.                     res = cnt[i][j];
  76.                     ei = i + 1;
  77.                     ej = j + 1;
  78.                 }
  79.             }
  80.         }
  81.     }
  82.     cout << ei << " " << ej << endl;
  83.    
  84.    
  85.    
  86.     return 0;
  87. }
  88.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement