Codeforces 128 A. Statues

問題

8x8のマスの左下にMがいて、右上のマスにAがいる。
Mを動かしてAの居るマスに辿り着けたら勝ちである。


グリッドの中にはSがあり、Sは、Mが動いた後に、一マス下におちる。
MのいるマスにSが落ちてきたら負けである。
Mは上下左右斜めに隣接するマスに進むことができ、Sのある場所には進むことはできない。


最善を尽くしたときに、Mは勝つか判定せよ。

方針

メモ化して全探索。

ソースコード

set<vector<string> > s;
bool dfs(vector<string> v){
  if(s.count(v))return 0;
  s.insert(v);
  rep(i,8)rep(j,8)if(v[i][j]=='M'){
    for(int y=i-1;y<i+2;y++)for(int x=j-1;x<j+2;x++){
      if(y<0||x<0||y>=8||x>=8||v[y][x]=='S')continue;
      if(v[y][x]=='A')return 1;
      
      vector<string> nxt=v;
      nxt[i][j]='.'; nxt[y][x]='M';
      for(int a=7;a>=0;a--)rep(b,8)if(nxt[a][b]=='S'){
        nxt[a][b]='.';
        if(a<7){
          if(nxt[a+1][b]=='M')goto FAIL;
          nxt[a+1][b]='S';
        }
      }
      if(dfs(nxt))return 1;
      FAIL:;
    }
  }
  return 0;
}
void run(){
  vector<string> in(8);
  rep(i,8)cin>>in[i];
  s.clear();
  cout<<(dfs(in)?"WIN":"LOSE")<<endl;
}