AOJ 0190 Eleven Puzzle

問題

Eleven Puzzle。

解法

BFSだと間に合わない。地球は爆発しないよね。

id:nanikakaさんのはてなダイアリーで両側探索というものがあるのを知った、 実装はJavaだったので見ずに勘で実装してみた。

一発AC。

嬉しかったです。

コード

vi p, next, now;
vector<vector<int> >dir(13);

int main(){
  rep(i, 13) if(i == 0 || i == 12) p.push_back(0); else p.push_back(i);

  dir[0].push_back(2);
  dir[1].push_back(2); dir[1].push_back(5);
  dir[2].push_back(0); dir[2].push_back(1); dir[2].push_back(3); dir[2].push_back(6);
  dir[3].push_back(2); dir[3].push_back(7);
  dir[4].push_back(5);
  dir[5].push_back(1); dir[5].push_back(4); dir[5].push_back(6); dir[5].push_back(9);
  dir[6].push_back(2); dir[6].push_back(5); dir[6].push_back(7); dir[6].push_back(10);
  dir[7].push_back(3); dir[7].push_back(6); dir[7].push_back(8); dir[7].push_back(11);
  dir[8].push_back(7);
  dir[9].push_back(5); dir[9].push_back(10);
  dir[10].push_back(6); dir[10].push_back(9); dir[10].push_back(11); dir[10].push_back(13);
  dir[11].push_back(7); dir[11].push_back(10);
  dir[12].push_back(10);

  map<vi, int>m;
  queue<vi>q;
  q.push(p);
  m[p] = 0;
  rep(i, 10){
    int qsize = q.size();
    rep(j, qsize){
      now = q.front(); q.pop();
      rep(k, 13){
    if(now[k] != 0) continue;
    rep(d, dir[k].size()){
      next = now;
      swap(next[k], next[dir[k][d]]);
      if(m.count(next) != 0) continue;
      m[next] = i+1;
      q.push(next);
    }
      }
    }
  }

  p.resize(13);
  while(scanf("%d", &p[0]) && p[0] != -1){
    REP(i, 1, 13) scanf("%d", &p[i]);

    map<vi, int>dist;
    queue<vi>q;
    q.push(p);
    dist[p] = 0;
    if(m.count(p) != 0){
      printf("%d\n", m[p]);
      goto e;
    }

    rep(i, 10){
      int qsize = q.size();
      rep(j, qsize){
    now = q.front(); q.pop();
    rep(k, 13){
      if(now[k] != 0) continue;
      rep(d, dir[k].size()){
        next = now;
        swap(next[k], next[dir[k][d]]);
        if(m.count(next) != 0){
          printf("%d\n", m[next]+i+1);
          goto e;
        }
        if(dist.count(next) != 0) continue;
        dist[next] = i+1;
        q.push(next);
      }
    }
      }
    }
    puts("NA");
  e:;
  }
  return 0;
}