Advertisement
Guest User

Untitled

a guest
Oct 15th, 2018
288
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.83 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define f first
  3. #define s second
  4. #define mk make_pair
  5. using namespace std;
  6. int dx[]={0,0,1,-1};
  7. int dy[]={1,-1,0,0};
  8. int n,m,d;
  9. vector <string> g;
  10. bool valid (int i,int j){
  11.     return i>=0 && j>=0 && i<n && j<m;
  12. }
  13. int x0,y0,xf,yf;
  14. int main (){
  15.     ios_base::sync_with_stdio(0),cin.tie(0);
  16.     cin>>n>>m>>d;
  17.     bool  death[n+4][m+4];
  18.     int dist[n+4][m+4];
  19.     memset(death,false,sizeof death);
  20.     for (int i=0;i<n;i++)
  21.         for (int j=0;j<m;j++) dist[i][j]=1e9;
  22.     g=vector<string> (n);
  23.     for (int i=0;i<n;i++)
  24.         cin>>g[i];
  25.     queue <pair<pair<int,int>,int>> q;
  26.     for (int i=0;i<n;i++)
  27.     for (int j=0;j<m;j++){
  28.         if (g[i][j]=='M')
  29.             q.push(mk(mk(i,j),0));
  30.         if (g[i][j]=='S') x0=i,y0=j;
  31.         if (g[i][j]=='F') xf=i,yf=j;
  32.  
  33.     }
  34.     while (!q.empty()){
  35.         auto cur =q.front();
  36.         death[cur.f.f][cur.f.s]=1;
  37.         q.pop();
  38.         for (int i=0;i<4;i++){
  39.             int xx=cur.f.f+dx[i];
  40.             int yy=cur.f.s+dy[i];
  41.             if (!valid (xx,yy) or death[xx][yy] or cur.s+1>d) continue;
  42.             q.push(mk(mk(xx,yy),cur.s+1));
  43.         }
  44.     }
  45.  
  46.     queue <pair<int,int>> pq;
  47.     if (death[x0][y0]==0)
  48.     pq.push(mk(x0,y0));
  49.     dist[x0][y0]=0;
  50.     while (!pq.empty()){
  51.         auto cur =pq.front();
  52.         pq.pop();
  53.         if (cur.f==xf && cur.s==yf){
  54.                 cout<<((dist[xf][yf]==1e9)?-1:dist[xf][yf]);
  55.                 return 0;
  56.         }
  57.         for (int i=0;i<4;i++){
  58.             int xx=cur.f+dx[i];
  59.             int yy=cur.s+dy[i];
  60.             if (valid (xx,yy) && dist[xx][yy]==(1e9) && death[xx][yy]==false){
  61.             dist[xx][yy]=1+dist[cur.f][cur.s];
  62.             death[xx][yy]=1;
  63.             pq.push(mk(xx,yy));
  64.             }
  65.         }
  66.     }
  67.     cout<<((dist[xf][yf]==1e9)?-1:dist[xf][yf]);
  68.  
  69.  
  70.  
  71. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement