SHARE
TWEET

1643TLE27

thouxanbanuno Nov 8th, 2019 99 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define pb push_back
  3. using namespace std;
  4. vector<vector<char> >g;
  5. vector<vector<bool> >used;
  6. vector<vector<int> > d;
  7. vector<vector<pair<int,int> > >  t;
  8. int n,m;
  9. int res1=-1,res2=-1;
  10. int dx[] = {-1, -1, -1,  0, 1, 1,  1,  0};
  11. int dy[] = {-1,  0,  1,  1, 1, 0, -1, -1};
  12. int bfs(int x, int y){
  13.     queue<pair<int,int> > q;
  14.     q.push({x,y});
  15.     while(!q.empty()){
  16.  
  17.         pair<int,int> to=q.front();
  18.       /*  if(to.first==2 && to.second==0){
  19.             cout<<"=="<<d[to.first][to.second]<<endl;
  20.  
  21.         }*/
  22.        
  23.        //cout<<to.first<<' '<<to.second<<endl;
  24.        //cout<<used[0][6]<<' '<<endl;
  25.         used[to.first][to.second]=1;
  26.         if(g[to.first][to.second]=='!'){
  27.             res1=d[to.first][to.second];
  28.         }
  29.         if(g[to.first][to.second]=='$'){
  30.             res2=d[to.first][to.second];
  31.         }
  32.         q.pop();
  33.          if(isalpha(g[to.first][to.second])){
  34.                 for(int h=0; h<t[g[to.first][to.second]-'A'].size(); h++){
  35.                 pair<int,int> newto=t[g[to.first][to.second]-'A'][h];
  36.                 if(!used[newto.first][newto.second]){
  37.                     q.push({newto.first,newto.second});
  38.                   //cout<<newto.first<<newto.second<<' '<<to.first<<to.second<<endl;
  39.                   //cout<<d[to.first][to.second]<<endl;
  40.                   used[newto.first][newto.second]=1;
  41.                     d[newto.first][newto.second]=d[to.first][to.second];
  42.                   //  cout<<d[newto.first][newto.second]<<' ';
  43.                 }
  44.          }
  45.          }
  46.  
  47.         for(int i=0; i<8; i++){
  48.             pair<int,int> cop=make_pair(to.first+dx[i], to.second+dy[i]);
  49.                 if(cop.first>=0 && cop.first<n && cop.second>=0 && cop.second<m && g[cop.first][cop.second]!='#'){
  50.                     if(!used[cop.first][cop.second]){
  51.                     q.push(cop);
  52.                     used[cop.first][cop.second]=1;
  53.                     d[cop.first][cop.second]=d[to.first][to.second]+1;
  54.                          }
  55.                     else{
  56.                         if(d[cop.first][cop.second]>d[to.first][to.second]+1){
  57.                             d[cop.first][cop.second]=d[to.first][to.second]+1;
  58.                         }
  59.                     }
  60.             /*if(cop.first==2 && cop.second==0){
  61.             cout<<"=="<<d[cop.first][cop.second]<<endl;*/
  62.  
  63.  
  64.             }
  65.         }
  66.     }
  67.     if(res1==-1 || res2==-1) return -1;
  68.     return(max(++res1,++res2));
  69. }
  70. int main(){
  71.     ios_base::sync_with_stdio(false);
  72.     cin.tie(0);
  73.     cin>>n>>m;
  74.      t.resize(30,vector<pair<int,int> >());
  75.     g.resize(n,vector<char>(m));
  76.     d.resize(n,vector<int> (m));
  77.     used.resize(n,vector<bool>(m,0));
  78.     char a;
  79.     pair<int,int> kate,jelo,krep;
  80.     string str;
  81.     for(int i=0; i<n; i++){
  82.         cin>>str;
  83.         for(int j=0; j<str.size(); j++){
  84.             g[i][j]=str[j];
  85.             if(str[j]=='$') kate={i,j};
  86.             else if(str[j]=='!') jelo={i,j};
  87.             else if(str[j]=='*'){ krep={i,j};
  88.             g[i][j]='#';
  89.             }
  90.             else if(isalpha(str[j]))
  91.                 t[g[i][j]-'A'].emplace_back(i,j);
  92.         }
  93.     }
  94.  
  95.  
  96.         vector<int>ans;
  97.     for(int i=0; i<8; i++){
  98.         pair<int,int> v=make_pair(krep.first+dx[i],krep.second+dy[i]);
  99.         if(v.first>=0 && v.first<n && v.second>=0 && v.second<m && g[v.first][v.second]!='#'){
  100.             ans.pb(bfs(v.first,v.second));
  101.              d.assign(n,vector<int>(m,0));
  102.              used.assign(n,vector<bool>(m,0));
  103.         }
  104.     }
  105.     int mn=1e9;
  106.     for(int i=0; i<ans.size(); i++){
  107.         if(mn>ans[i])
  108.             mn=ans[i];
  109.     }
  110.     if(mn==-1 || mn==1e9)
  111.         cout<<"Impossible";
  112.     else cout<<mn;
  113.  
  114.  
  115.  
  116.     return 0;
  117. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top