Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-05-06

SRM223 Div1 Hard: RevolvingDoor

| 01:37 | SRM223 Div1 Hard: RevolvingDoor - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM223 Div1 Hard: RevolvingDoor - naoya_t@topcoder SRM223 Div1 Hard: RevolvingDoor - naoya_t@topcoder のブックマークコメント

Algorithm Tutorials: How To Find a Solution (by Dumitru) より

  • 1000点問題!
  • マップ上のSからEまで行くのに、回転ドアを最低何回回転させる必要があるか。(辿り着けない場合は-1)
  • 確かにBFSであります
  • ドアの回転状態を持ち回る必要がある。listとか使うか?
  • 問題よく読め!ドアは最大10個しかない!10bit!
  • 1つ回転数を少なく答えるケースがある・・・ゴールにドアがかぶっている場合にドアの状態を反映していなかった
  • 時間かかったけどとりあえず全テストケース通るようになった!
  • submit ... 317.84points (146'39'')
  • 本番は3問で75分なんですけど><
  • しかしFailed System Test: TLE×1
"S                                                 ",
"                                                  ",
"                                                  ",
"-O--O--O--O--O--O--O--O--O--O-                    ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                  ",
"                                                 #",
"                                                #E"
  • 確かにこれはゴールできないw
  • ドアぐるぐる回しながら全ての状態(50x50x2^10)を走査することになるだろう
  • ステップ数数え始める前に、ドア無視してflood fillしておくか
  • どうやるんだっけ...queueだと重複あってなかなか進まない。set使うか
  • できた
  • →Passed System Test
  • 最終的なコード:
#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define found(s,e)  ((s).find(e)!=(s).end())

class RevolvingDoors {
  int w,h;
  
  inline int cell(int x,int y){return (y<<6)|x;}
  inline int cellx(int c){return c&63;}
  inline int celly(int c){return c>>6;}

  inline int left(int c){return c-1;}
  inline int right(int c){return c+1;}
  inline int up(int c){return c-64;}
  inline int down(int c){return c+64;}
 public:
  int turns(vector<string> m) {
    h=sz(m),w=sz(m[0]);

    vector<bool> road(4096,false);
    vector<vector<int> > score(4096);
    vector<int> doors, doormap(4096,-1), doorof(4096,-1);
    int doorcnt=0, start_cell=0, end_cell=0;

    // pass1
    rep(y,h){
      rep(x,w){
        int c=cell(x+1,y+1);
        switch(m[y][x]){
          case 'S': road[c]=true; start_cell=c; break;
          case 'E': road[c]=true; end_cell=c; break;
          case 'O': road[c]=false; doormap[c]=doorcnt++; doors.pb(c); break;
          case '-': road[c]=true; break;
          case '|': road[c]=true; break;
          case '#': road[c]=false; break;
          case ' ': road[c]=true; break;
        }
      }
    }
    
    int nm=1<<doorcnt;
    rep(i,4096){
      score[i].resize(nm); rep(j,nm) score[i][j]=INT_MAX;
    }
    
    int doorstat = 0;
    // pass2
    rep(y,h){
      rep(x,w){
        int c=cell(x+1,y+1), r,l,u,d,did=-1;
        switch(m[y][x]){
          case 'O': case '#': break;
          case '-':
            r=right(c),l=left(c);
            if(doormap[r]>=0) did=doormap[r];
            else if(doormap[l]>=0) did=doormap[l];
            doorof[c]=did;
            // doorstat |= (1 << did);
            break;
          case '|':
            u=up(c),d=down(c);
            if(doormap[u]>=0) did=doormap[u];
            else if(doormap[d]>=0) did=doormap[d];
            doorof[c]=did;
            doorstat |= (1 << did);
            break;
          case ' ': case 'S': case 'E':
            r=right(c),l=left(c),u=up(c),d=down(c);
            if(doormap[r]>=0) did=doormap[r];
            else if(doormap[l]>=0) did=doormap[l];
            else if(doormap[u]>=0) did=doormap[u];
            else if(doormap[d]>=0) did=doormap[d];
            doorof[c]=did;
            break;
        }
      }
    }

    // check impasse: flood fill (あとから追加)
    vector<bool> reach(4096,false);
    set<int> s0;
    s0.insert(start_cell); // reach[start_cell]=true;
    while(!s0.empty()){
      typeof(s0.begin()) it = s0.begin();
      int c=*it; s0.erase(it);
      reach[c]=true;
      if (c==end_cell) break;
      printf(" I %d %d¥n", cellx(c),celly(c));
      int nxt[4] = { up(c), right(c), down(c), left(c) };
      rep(i,4){
        int c_=nxt[i];
        if(!road[c_]) continue;
        if(!reach[c_]) s0.insert(c_);
      }
    }
    if(!reach[end_cell]) return -1;

    // let's探索
    priority_queue<pair<int,pair<int,int> > > pq; // -score,loc,doorstat
    pq.push(make_pair(0,make_pair(start_cell,doorstat)));

    vector<int> goaled; int goaled_min=INT_MAX;
    
    while(!pq.empty()){
      pair<int,pair<int,int> > p=pq.top(); pq.pop();
      int sc=-p.first, c=p.second.first, ds=p.second.second;
      if (sc>goaled_min) break;
      if (score[c][ds]<=sc) continue;
      score[c][ds]=sc;
      if(c==end_cell) {
        if (sc<goaled_min) {
          goaled_min=sc; goaled.pb(sc); }
        continue;
      }
      int nxt[4] = { up(c), right(c), down(c), left(c) };
      rep(i,4){
        int c_=nxt[i];
        if(!road[c_]) continue;
        int did=doorof[c_];
        if(did>=0){ // ドアな可能性あり
          int dcell=doors[did], ofs=c_-dcell; if(ofs<0) ofs=-ofs;
          int mask=1<<did;
          int st=ds & mask;
          if(st && ofs==64) { // |
            if (c-c_ != c_-dcell){ //回転出来る
              pq.push(make_pair(-(sc+1),make_pair(c_,ds-mask)));
            }
          } else if(!st && ofs==1){ // -
            if (c-c_ != c_-dcell){ //回転出来る
              pq.push(make_pair(-(sc+1),make_pair(c_,ds+mask)));
            }
          } else {
            // ドアなし
            pq.push(make_pair(-sc,make_pair(c_,ds)));
          }
        }else{
          pq.push(make_pair(-sc,make_pair(c_,ds)));
        }
      }
    }

    if(sz(goaled) > 0){
      sort(all(goaled));
      return goaled[0];
    } else {
      return -1;
    }
  }
};
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090506