Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define f first
- #define s second
- #define mk make_pair
- using namespace std;
- int dx[]={0,0,1,-1};
- int dy[]={1,-1,0,0};
- int n,m,d;
- vector <string> g;
- bool valid (int i,int j){
- return i>=0 && j>=0 && i<n && j<m;
- }
- int x0,y0,xf,yf;
- int main (){
- ios_base::sync_with_stdio(0),cin.tie(0);
- cin>>n>>m>>d;
- bool death[n+4][m+4];
- int dist[n+4][m+4];
- memset(death,false,sizeof death);
- for (int i=0;i<n;i++)
- for (int j=0;j<m;j++) dist[i][j]=1e9;
- g=vector<string> (n);
- for (int i=0;i<n;i++)
- cin>>g[i];
- queue <pair<pair<int,int>,int>> q;
- for (int i=0;i<n;i++)
- for (int j=0;j<m;j++){
- if (g[i][j]=='M')
- q.push(mk(mk(i,j),0));
- if (g[i][j]=='S') x0=i,y0=j;
- if (g[i][j]=='F') xf=i,yf=j;
- }
- while (!q.empty()){
- auto cur =q.front();
- death[cur.f.f][cur.f.s]=1;
- q.pop();
- for (int i=0;i<4;i++){
- int xx=cur.f.f+dx[i];
- int yy=cur.f.s+dy[i];
- if (!valid (xx,yy) or death[xx][yy] or cur.s+1>d) continue;
- q.push(mk(mk(xx,yy),cur.s+1));
- }
- }
- queue <pair<int,int>> pq;
- if (death[x0][y0]==0)
- pq.push(mk(x0,y0));
- dist[x0][y0]=0;
- while (!pq.empty()){
- auto cur =pq.front();
- pq.pop();
- if (cur.f==xf && cur.s==yf){
- cout<<((dist[xf][yf]==1e9)?-1:dist[xf][yf]);
- return 0;
- }
- for (int i=0;i<4;i++){
- int xx=cur.f+dx[i];
- int yy=cur.s+dy[i];
- if (valid (xx,yy) && dist[xx][yy]==(1e9) && death[xx][yy]==false){
- dist[xx][yy]=1+dist[cur.f][cur.s];
- death[xx][yy]=1;
- pq.push(mk(xx,yy));
- }
- }
- }
- cout<<((dist[xf][yf]==1e9)?-1:dist[xf][yf]);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement