Advertisement
Josif_tepe

Untitled

Apr 7th, 2021
123
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.86 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7.     int n;
  8.     int m;
  9.     cin>>n>>m;
  10.     char matrica[n][m];
  11.  
  12.     queue<int>q;
  13.     queue<int>q1;
  14.  
  15.     int e1;
  16.     int e2;
  17.     int s1;
  18.     int s2;
  19.     int najgolem=0;
  20.  
  21.      int distance_s[n][m];
  22.     int distance_e[n][m];
  23.  
  24.     for(int y=0; y<n; y++){
  25.         for(int y1=0; y1<m; y1++){
  26.             distance_s[y][y1]=-1;
  27.             distance_e[y][y1]=-1;
  28.         }
  29.     }
  30.  
  31.  
  32.     for(int x=0; x<n; x++){
  33.         for(int x1=0; x1<m; x1++){
  34.             cin>>matrica[x][x1];
  35.             if(matrica[x][x1]=='E'){
  36.                 e1=x;
  37.                 e2=x1;
  38.             }
  39.             if(matrica[x][x1]=='S'){
  40.                 s1=x;
  41.                 s2=x1;
  42.             }
  43.         }
  44.     }
  45.     bool matrica1[n][m];
  46.     for(int u=0; u<n; u++){
  47.         for(int u1=0; u1<m; u1++){
  48.             matrica1[u][u1]=false;
  49.         }
  50.     }
  51.      bool matrica2[n][m];
  52.     for(int u3=0; u3<n; u3++){
  53.         for(int u2=0; u2<m; u2++){
  54.             matrica2[u3][u2]=false;
  55.         }
  56.     }
  57.  
  58.  
  59.  
  60.     q.push(s1);
  61.     q.push(s2);
  62.     q.push(0);
  63.  
  64.     int niza1[]{0,0,-1,1};
  65.     int niza2[]{-1,1,0,0};
  66.  
  67.  
  68.  
  69.     while(!q.empty()){
  70.     int ts1=q.front();
  71.     q.pop();
  72.     int ts2=q.front();
  73.     q.pop();
  74.     int stapki=q.front();
  75.     q.pop();
  76.  
  77.         if(matrica[ts1][ts2] == 'E') {
  78.             cout << stapki << endl;
  79.             return 0;
  80.         }
  81.     if(matrica[ts1][ts2]=='#'){
  82.       distance_s[ts1][ts2]=stapki;
  83.       continue;
  84.     }
  85.  
  86.     for(int k1=0; k1<4; k1++){
  87.         int cs1=ts1+niza1[k1];
  88.         int cs2=ts2+niza2[k1];
  89.  
  90.  
  91.  
  92.         if((cs1>=0)and(cs1<n)and(matrica1[cs1][cs2]==false)and(cs2>=0)and(cs2<m)){
  93.             q.push(cs1);
  94.             q.push(cs2);
  95.             q.push(stapki+1);
  96.             matrica1[cs1][cs2]=true;
  97.  
  98.         }
  99.     }
  100.     }
  101.  
  102.     q1.push(e1);
  103.     q1.push(e2);
  104.     q1.push(0);
  105.  
  106.     while(!q1.empty()){
  107.     int te1=q1.front();
  108.     q1.pop();
  109.     int te2=q1.front();
  110.     q1.pop();
  111.     int stapki1=q1.front();
  112.     q1.pop();
  113.  
  114.     if(matrica[te1][te2]=='#'){
  115.       distance_e[te1][te2]=stapki1;
  116.       continue;
  117.     }
  118.  
  119.     for(int k2=0; k2<4; k2++){
  120.         int ce1=te1+niza1[k2];
  121.         int ce2=te2+niza2[k2];
  122.      if((ce1>=0)and(ce1<n)and(matrica2[ce1][ce2]==false)and(ce2>=0)and(ce2<m)){
  123.         q1.push(ce1);
  124.         q1.push(ce2);
  125.         q1.push (stapki1+1);
  126.         matrica2[ce1][ce2]=true;
  127.     }
  128.     }
  129.     }
  130.  
  131.     for(int l=0; l<n; l++){
  132.         for(int l1=0; l1<m; l1++){
  133.             if((distance_e[l][l1]!=-1)and(distance_s[l][l1]!=-1)){
  134.                 int c1=distance_e[l][l1]+distance_s[l][l1];
  135.  
  136.                 if(c1>najgolem){
  137.                     najgolem=c1;
  138.                 }
  139.  
  140.             }
  141.         }
  142.     }
  143.     if(najgolem>0){
  144.         cout<<najgolem;
  145.         return 0;
  146.     }
  147.     cout<<"-1";
  148.     return 0;
  149. }
  150.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement