Advertisement
Josif_tepe

Untitled

Mar 14th, 2023
567
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.68 KB | None | 0 0
  1. #include <iostream>
  2. //#include <bits/stdc+/+.h>
  3. #include <vector>
  4. #include <queue>
  5. #include <cstring>
  6. #define ll long long
  7.  
  8. using namespace std;
  9. int n,m;
  10. int main()
  11. {
  12. int n,m;
  13. cin >> n >> m;
  14. char mat[n][m];
  15. int di[]={-1,1,0,0};
  16. int dj[]={0,0,1,-1};
  17. int si,sj,ei,ej;
  18. int k;cin>>k;
  19. for(int i=0;i<n;i++){
  20.     for(int j=0;j<m;j++){
  21.         cin >> mat[i][j];
  22.         if(mat[i][j] == 'M'){
  23.             si =i;
  24.             sj = j;
  25.         }
  26.         if(mat[i][j] == 'V'){
  27.             ei =i;
  28.             ej = j;
  29.         }
  30.     }
  31. }
  32. queue<int>q;
  33. vector<vector<bool>> visited(n+1,vector<bool>(m+1,false));
  34. q.push(si);
  35. q.push(sj);
  36. visited[si][sj]=true;
  37. vector<pair<int,int>> cell;
  38. int dist[n][m];
  39. while(!q.empty()){
  40.     int ci = q.front();
  41.     q.pop();
  42.     int cj = q.front();
  43.     q.pop();
  44.     visited[ci][cj] = true;
  45.     if(mat[ci][cj] == 'V'){
  46.         cout << "DA"<<endl;
  47.         return 0;
  48.     }
  49.     for(int i =0;i<4;i++){
  50.         int ti = ci+di[i];
  51.         int tj = cj+dj[i];
  52.         if(ti>=0 and ti<n and tj>=0 and tj<m and !visited[ti][tj]){
  53.             if(mat[ti][tj] == '#'){
  54.                 cell.push_back(make_pair(ci,cj));
  55.             }
  56.             else{
  57.             q.push(ti);
  58.             q.push(tj);
  59.             visited[ti][tj]=true;
  60.             }
  61.         }
  62.     }
  63. }
  64. for(int i = 0;i<n+1;i++){
  65.     for(int j =0;j<m+1;j++){
  66.         visited[i][j] =false;
  67.     }
  68. }
  69. for(int i =0;i<cell.size();i++){
  70.     int ci = cell[i].first;
  71.     int cj = cell[i].second;
  72.     dist[ci][cj]=0;
  73.     q.push(ci);
  74.     q.push(cj);
  75.     q.push(0);
  76.     visited[ci][cj] =true;
  77. }
  78.  
  79. while(!q.empty()){
  80.     int ci = q.front();
  81.     q.pop();
  82.     int cj = q.front();
  83.     q.pop();
  84.     int pat = q.front();
  85.     q.pop();
  86.  
  87.     dist[ci][cj] = pat;
  88.     for(int i =0;i<4;i++){
  89.         int ti = ci+di[i];
  90.         int tj = cj+dj[i];
  91.         if(ti>=0 and ti<n and tj>=0 and tj<m and !visited[ti][tj]){
  92.             q.push(ti);
  93.             q.push(tj);
  94.             q.push(pat+1);
  95.             dist[ti][tj] = pat+1;
  96.             visited[ti][tj] = true;
  97.         }
  98.     }
  99.  
  100. }
  101. for(int i = 0;i<n+1;i++){
  102.     for(int j =0;j<m+1;j++){
  103.         visited[i][j] =false;
  104.     }
  105. }
  106. q.push(ei);
  107. q.push(ej);
  108. visited[ei][ej] = true;
  109. while(!q.empty()){
  110.     int ci = q.front();
  111.     q.pop();
  112.     int cj =  q.front();
  113.     q.pop();
  114.  
  115.     if(dist[ci][cj]<=k){
  116.         cout << "DA";
  117.         return 0;
  118.     }
  119.     for(int i =0;i<4;i++){
  120.         int ti =ci +di[i];
  121.         int tj = cj+dj[i];
  122.  
  123.         if(ti>=0 and ti<n and tj>=0 and tj<m and  !visited[ti][tj] and mat[ti][tj]!='#'){
  124.             q.push(ti);
  125.             q.push(tj);
  126.             visited[ti][tj] =true;
  127.         }
  128.     }
  129. }
  130. cout << "NE";
  131. }
  132.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement