Advertisement
YEZAELP

TOI13: Robot

Oct 20th, 2020 (edited)
124
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.57 KB | None
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int INF = 2e9;
  6. using pi = pair <int, int>;
  7. using pii = pair <int, pi>;
  8. int n, m;
  9. char ar[2001][2001];
  10.  
  11. int idx[] = {0, 0, -1, 1};
  12. int idy[] = {1, -1, 0, 0};
  13. map <pi, int> ans;
  14.  
  15. bool position(int i, int j){
  16.     return i >= 1 and i <= n and j >=1 and j <= m;
  17. }
  18.  
  19. vector < vector <int>> dis(2001, vector <int> (2001, INF));
  20. bool visited[2001][2001];
  21.  
  22. int main(){
  23.  
  24.  
  25.     scanf("%d%d", &n, &m);
  26.  
  27.     queue <pii> q;
  28.  
  29.     for(int i=1;i<=n;i++){
  30.         for(int j=1;j<=m;j++){
  31.             scanf(" %c", &ar[i][j]);
  32.             if(ar[i][j] == 'X') q.push({0, {i ,j}});
  33.         }
  34.     }
  35.  
  36.     int cnt = 0, sum = 0;
  37.     while(q.size() > 0){
  38.         int ui = q.front().second.first;
  39.         int uj = q.front().second.second;
  40.         int Dis = q.front().first;
  41.         q.pop();
  42.  
  43.         if(visited[ui][uj])
  44.             continue;
  45.         visited[ui][uj] = true;
  46.  
  47.         if(ar[ui][uj] == 'A'){
  48.             cnt ++;
  49.             sum += Dis;
  50.         }
  51.  
  52.         for(int d=0;d<4;d++){
  53.             int vi, vj;
  54.             vi = ui + idx[d];
  55.             vj = uj + idy[d];
  56.             if(!position(vi, vj) or visited[vi][vj] or ar[vi][vj] == 'W')
  57.                 continue;
  58.             if(ar[vi][vj] == 'X'){
  59.                 dis[vi][vj] = 0;
  60.                 q.push({0, {vi, vj}});
  61.             }
  62.             else if(Dis + 1 < dis[vi][vj]){
  63.                 dis[vi][vj] = Dis + 1;
  64.                 q.push({Dis + 1,{vi, vj}});
  65.             }
  66.         }
  67.     }
  68.  
  69.     printf("%d %d", cnt, 2 * sum);
  70.  
  71.     return 0;
  72. }
  73.  
  74.  
Advertisement
RAW Paste Data Copied
Advertisement