Advertisement
Josif_tepe

Untitled

Oct 31st, 2021
125
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.73 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. using namespace std;
  4.  
  5. int main()
  6. {
  7.     int a,b;
  8.     cin>>a>>b;
  9.     char mat[a][b];
  10.     queue<int>Q;
  11.     int poseten[a][b];
  12.     int rs,ks,re,ke;
  13.     for(int i=0;i<a;i++)
  14.     {
  15.         for(int j=0;j<b;j++)
  16.         {
  17.             cin>>mat[i][j];
  18.             if(mat[i][j]=='S')
  19.             {
  20.                 rs=i;
  21.                 ks=j;
  22.             }
  23.             if(mat[i][j]=='E')
  24.             {
  25.                 re=i;
  26.                 ke=j;
  27.             }
  28.             poseten[i][j]=false;
  29.         }
  30.     }
  31.     int s[a][b];
  32.     int e[a][b];
  33.     for(int i=0;i < a;i++)
  34.     {
  35.         for(int j=0;j<b;j++)
  36.         {
  37.             s[i][j]=-1;
  38.             e[i][j]=-1;
  39.         }
  40.     }
  41.  
  42.     Q.push(rs);
  43.     Q.push(ks);
  44.     poseten[rs][ks] = true;
  45.     int kolkuS=0;
  46.     Q.push(kolkuS);
  47.         while(!Q.empty() )
  48.         {
  49.            int ci=Q.front();
  50.            Q.pop();
  51.            int cj=Q.front();
  52.            Q.pop();
  53.            int n=Q.front();
  54.            Q.pop();
  55.             if(ci == re and cj == ke) {
  56.                 cout << n << endl;
  57.                 return 0;
  58.             }
  59.            if(cj+1<b && poseten[ci][cj+1]!=true && mat[ci][cj+1]!='#')
  60.            {
  61.                Q.push(ci);
  62.                Q.push(cj+1);
  63.                Q.push(n+1);
  64.                poseten[ci][cj+1]=true;
  65.            }
  66.            if(cj+1<b && poseten[ci][cj+1]!=true && mat[ci][cj+1]=='#')
  67.            {
  68.                s[ci][cj+1]=n+1;
  69.            }
  70.            if(cj-1>=0 && poseten[ci][cj-1]!=true && mat[ci][cj-1]!='#')
  71.            {
  72.                Q.push(ci);
  73.                Q.push(cj-1);
  74.                Q.push(n+1);
  75.                poseten[ci][cj-1]=true;
  76.            }
  77.            if(cj-1>=0 && poseten[ci][cj-1]!=true && mat[ci][cj-1]=='#')
  78.            {
  79.                s[ci][cj-1]=n+1;
  80.            }
  81.            if(ci+1<a && poseten[ci+1][cj]!=true && mat[ci+1][cj]!='#')
  82.            {
  83.                Q.push(ci+1);
  84.                Q.push(cj);
  85.                Q.push(n+1);
  86.                poseten[ci+1][cj]=true;
  87.            }
  88.            if(ci+1<a && poseten[ci+1][cj]!=true && mat[ci+1][cj]=='#')
  89.            {
  90.                s[ci+1][cj]=n+1;
  91.            }
  92.            if(ci-1>=0 && poseten[ci-1][cj]!=true && mat[ci-1][cj]!='#')
  93.            {
  94.                Q.push(ci-1);
  95.                Q.push(cj);
  96.                Q.push(n+1);
  97.                poseten[ci-1][cj]=true;
  98.            }
  99.            if(ci-1>=0 && poseten[ci-1][cj]!=true && mat[ci-1][cj]=='#')
  100.            {
  101.                s[ci-1][cj]=n+1;
  102.            }
  103.         }
  104.     for(int i =0 ; i < a; i++) {
  105.         for(int j= 0; j < b; j++) {
  106.             poseten[i][j] = false;
  107.         }
  108.     }
  109.     Q.push(re);
  110.     Q.push(ke);
  111.     poseten[re][ke] = true;
  112.     int kolkuE=0;
  113.     Q.push(kolkuE);
  114.         while(!Q.empty() )
  115.         {
  116.            int ci=Q.front();
  117.            Q.pop();
  118.            int cj=Q.front();
  119.            Q.pop();
  120.            int n=Q.front();
  121.            Q.pop();
  122.            if(cj+1<b && poseten[ci][cj+1]!=true && mat[ci][cj+1]!='#')
  123.            {
  124.                Q.push(ci);
  125.                Q.push(cj+1);
  126.                Q.push(n+1);
  127.                poseten[ci][cj+1]=true;
  128.            }
  129.            if(cj+1<b && poseten[ci][cj+1]!=true && mat[ci][cj+1]=='#')
  130.            {
  131.                e[ci][cj+1]=n+1;
  132.            }
  133.            if(cj-1>=0 && poseten[ci][cj-1]!=true && mat[ci][cj-1]!='#')
  134.            {
  135.                Q.push(ci);
  136.                Q.push(cj-1);
  137.                Q.push(n+1);
  138.                poseten[ci][cj-1]=true;
  139.            }
  140.            if(cj-1>=0 && poseten[ci][cj-1]!=true && mat[ci][cj-1]=='#')
  141.            {
  142.                e[ci][cj-1]=n+1;
  143.            }
  144.            if(ci+1<a && poseten[ci+1][cj]!=true && mat[ci+1][cj]!='#')
  145.            {
  146.                Q.push(ci+1);
  147.                Q.push(cj);
  148.                Q.push(n+1);
  149.                poseten[ci+1][cj]=true;
  150.            }
  151.            if(ci+1<a && poseten[ci+1][cj]!=true && mat[ci+1][cj]=='#')
  152.            {
  153.                e[ci+1][cj]=n+1;
  154.            }
  155.            if(ci-1>=0 && poseten[ci-1][cj]!=true && mat[ci-1][cj]!='#')
  156.            {
  157.                Q.push(ci-1);
  158.                Q.push(cj);
  159.                Q.push(n+1);
  160.                poseten[ci-1][cj]=true;
  161.            }
  162.            if(ci-1>=0 && poseten[ci-1][cj]!=true && mat[ci-1][cj]=='#')
  163.            {
  164.                e[ci-1][cj]=n+1;
  165.            }
  166.         }
  167.         int najgolem=-1;
  168.         for(int i=0;i<a;i++)
  169.         {
  170.             for(int j=0;j<b;j++)
  171.             {
  172.                 if(s[i][j] != -1 and e[i][j] != -1 and najgolem<s[i][j]+e[i][j])
  173.                 {
  174.                     najgolem=s[i][j]+e[i][j];
  175.                 }
  176.             }
  177.         }
  178.         cout<<najgolem;
  179.     return 0;
  180. }
  181.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement