Advertisement
Josif_tepe

Untitled

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