Advertisement
Josif_tepe

Untitled

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