Advertisement
Josif_tepe

Untitled

May 5th, 2021
121
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.55 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <cstring>
  6.  
  7. using namespace std;
  8.  
  9. struct node{
  10. int x;
  11. int y;
  12. int distance;
  13. node(){
  14.  
  15. }
  16. node(int _x, int _y, int _distance){
  17. x=_x;
  18. y=_y;
  19. distance=_distance;
  20. }
  21. bool operator <(const node& temp)const{
  22. return distance<temp.distance;
  23. }
  24. };
  25.  
  26.  
  27. int main()
  28. {
  29. int n, m;
  30. cin>>n;
  31. cin>>m;
  32. char matrica[n][m];
  33. bool visited[n][m];
  34. int sy;
  35. int sx;
  36. int ex;
  37. int ey;
  38. int distance[n][m];
  39. vector<pair<int, int>>v;
  40. priority_queue<node>pq;
  41. queue<int>q;
  42. for(int y=0; y<n; y++){
  43.     for(int y1=0; y1<m; y1++){
  44.         visited[y][y1]=false;
  45.     }
  46. }
  47. for(int x=0; x<n; x++){
  48.     for(int x1=0; x1<m; x1++){
  49.         cin>>matrica[x][x1];
  50.       if(matrica[x][x1]=='G'){
  51.         q.push(x);
  52.         q.push(x1);
  53.         q.push(0);
  54.       }
  55.         if(matrica[x][x1]=='R'){
  56.         sx=x;
  57.         sy=x1;
  58.       }
  59.       if(matrica[x][x1]=='Z'){
  60.         ex=x;
  61.         ey=x1;
  62.       }
  63. }
  64. }
  65. for(int h=0; h<n; h++){
  66.     for(int h1=0; h1<m; h1++){
  67.         distance[h][h1]=-1;
  68.     }
  69. }
  70.  
  71.     int dx[]={1,0,-1,0};
  72.     int dy[]={0,1,0,-1};
  73.     while(!q.empty()){
  74.     int cx=q.front();
  75.     q.pop();
  76.     int cy=q.front();
  77.     q.pop();
  78.     int brojac=q.front();
  79.     q.pop();
  80.     if(matrica[cx][cy]=='G'){
  81.         distance[cx][cy]=0;
  82.         visited[cx][cy]=true;
  83.     }
  84.     for(int y=0; y<4; y++){
  85.         int tx=cx+dx[y];
  86.         int ty=cy+dy[y];
  87.     if((tx>=0)and(ty>=0)and(tx<n)and(ty<m)and(visited[tx][ty]==false)and(matrica[tx][ty]!='*')){
  88.        q.push(tx);
  89.        q.push(ty);
  90.        visited[tx][ty]=true;
  91.        distance[tx][ty]=brojac+1;
  92.        q.push(brojac+1);
  93.        }
  94.     }
  95.     }
  96.  
  97.  
  98.     for(int d=0; d<n; d++){
  99.         for(int d1=0; d1<m; d1++){
  100.             visited[d][d1]=false;
  101.             cout << distance[d][d1] << " " ;
  102.         }
  103.         cout << endl;
  104.     }
  105.  
  106.     pq.push(node(sx, sy, distance[sx][sy]));
  107.     while(!pq.empty()){
  108.     node c=pq.top();
  109.     pq.pop();
  110.     if((c.x==ex)and(c.y==ey)){
  111.         cout<<c.distance;
  112.         return 0;
  113.     }
  114.     for(int d2=0; d2<4; d2++){
  115.         int tx=c.x+dx[d2];
  116.         int ty=c.y+dy[d2];
  117.         if((ty>=0)and(tx>=0)and(tx<n)and(ty<m)and(visited[tx][ty]==false)and(matrica[tx][ty]='.')){
  118.           pq.push(node(tx, ty, min(distance[tx][ty], c.distance)));
  119.           visited[tx][ty]=true;
  120.         }
  121.     }
  122.     }
  123.     return 0;
  124. }
  125. /*
  126.  4 3 2 3 4 3 2 3 4
  127.  3 2 1 2 3 2 1 2 3
  128.  2 1 0 1 2 1 0 1 2
  129.  1 2 1 2 2 2 1 2 3
  130.  0 1 2 2 1 2 2 3 4
  131.  1 2 2 1 0 1 2 3 4
  132.  2 3 3 -1 -1 2 3 4 5
  133.  3 4 4 5 4 3 4 5 6
  134.  
  135.  */
  136.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement