Advertisement
Josif_tepe

Untitled

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