Submission #1187280

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
signed main(){
  string s[19];
  for(int i=0;i<19;i++) cin>>s[i];
 
  int sy,sx;
  vector<int> v;
  for(int i=0;i<19;i++){
    for(int j=0;j<15;j++){
      if(s[i][j]=='O') sy=i,sx=j;
      if(s[i][j]=='X') v.push_back(i*15+j);
    }
  }
   
  int n=v.size();
  int sb=(sy*15+sx)<<n;
   
  map<int,int> m;
  for(int i=0;i<n;i++) m[v[i]]=i;
 
  int ax[]={-1,-1,-1,0,0,1,1,1};
  int ay[]={-1,0,1,-1,1,-1,0,1};
   
  int ans=-1,mask=(1<<n)-1;
  priority_queue<P> q;
  q.push(P(0,sb));
  map<int,int> ms;
  ms[sb]=0;
   
  while(!q.empty()){
    P p=q.top();q.pop();
    int d=-p.first,b=p.second;
    int cy=(b>>n)/15,cx=(b>>n)%15;
    //cout<<(b>>n)<<" "<<cy<<" "<<cx<<" "<<d<<endl;
    if(ms[b]<d) continue;
    for(int k=0;k<8;k++){
      int ny=cy+ay[k],nx=cx+ax[k],nb=b&mask,nd=d+1;
      if(!m.count(ny*15+nx)) continue;
      //cout<<ny<<" "<<nx<<" "<<nb<<" "<<nd<<endl;
      if(nb&(1<<m[ny*15+nx])) continue;
      while(m.count(ny*15+nx)){
    if(nb&(1<<m[ny*15+nx])) break;
    //cout<<n<<":"<<m[ny*15+nx]<<" "<<nb<<" "<<(1<<m[ny*15+nx])<<endl;
    nb+=1<<m[ny*15+nx];
    ny+=ay[k];
    nx+=ax[k];
      }
      //cout<<ny<<" "<<nx<<" "<<ny*15+nx<<" "<<nb<<endl;
      if(ny==18&&0<=nx&&nx<15){
    ans=nd;
    goto END;
      }
      if(ny>18){
    ans=nd;
    goto END;
      }
      if(ny<0||nx<0||nx>=15) continue;
      nb+=(ny*15+nx)<<n;
      //cout<<nb<<" "<<(nb&mask)<<" "<<(nb>>n)<<endl;
      if(ms.count(nb)&&ms[nb]<=nd) continue;
      ms[nb]=nd;
      q.push(P(-nd,nb));
    }
  }
 END:
  cout<<ans<<endl;
  return 0;
}

Submission Info

Judge Result