naoya_t@topcoder

SRM233 Div1 Medium: SmartWordToy

過去問, 練習, Tutorials | 23:35 |

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

• 典型的なBFSの例
• 状態数が26^4しかない。隣のstateへの移動コストは全て1
• priority queue使ってみますた
• 優先順位の逆転方法、というかソートの向きの設定方法を思い出せないのでステップ数を負にして入れている。（←よくやる）
• 自作split()使ってます
• 197.58points (59'47'') デバッグコメント類を削除して（というか BEGIN CUT HERE / END CUT HEREで囲んで）submitしてるけど、この分量だとコメント部分を投稿前に消したりとかしなくても大丈夫そうなので、あと１分前後早く出せると思う
• Passed system test

class SmartWordToy {
  inline int state(int ch0,int ch1,int ch2,int ch3){
    return ((ch0-'a') << 15) | ((ch1-'a') << 10) | ((ch2-'a') << 5) | (ch3-'a');
  }
  inline int state_ch(int state,int pos){
    return (state >> (15 - 5*pos)) & 0x1f; // 0-25
  }
  int str2state(const string str){
    return state(str[0],str[1],str[2],str[3]);
  }
/*
  string state2str(int state){
    stringstream ss;
    rep(i,4) ss << 'a'+state_ch(state,0);
    return ss.str();
  }
*/
  int incr(int state, int pos){
    int ofs=15-5*pos;
    int ch=state_ch(state,pos);
    state &= ~(0x1f << ofs);
    int newstate=state|(((ch+1)%26)<<ofs);
    return newstate;
  }
  int decr(int state, int pos){
    int ofs=15-5*pos;
    int ch=state_ch(state,pos);
    state &= ~(0x1f << ofs);
    int newstate=state|(((ch+25)%26)<<ofs);
    return newstate;
  }
     
 public:
  int minPresses(string start, string finish, vector <string> forbid) {
    int s_state=str2state(start), f_state=str2state(finish);

    vector<int> passed(1048576,INT_MAX);
    tr(forbid,it){
      vector<string> ss = split(*it);
      int al=sz(ss[0]), bl=sz(ss[1]), cl=sz(ss[2]), dl=sz(ss[3]);
      rep(a,al){
        rep(b,bl){
          rep(c,cl){
            rep(d,dl){
              int st=state(ss[0][a], ss[1][b], ss[2][c], ss[3][d]);
              passed[st]=-1;// forbidden
            }
          }
        }
      }
    }
    if(passed[f_state]==-1) return -1;

    priority_queue<pair<int,int> > pq;
    pq.push(make_pair(0,s_state));

    while (!pq.empty()) {
      int step=-pq.top().first, st=pq.top().second, st_;
      pq.pop();
      if(st==f_state) return step;
      if(step < passed[st]){
        passed[st]=step;

        step++;
        rep(i,4){
          st_ = incr(st,i);
          if(passed[st_]>step) pq.push(make_pair(-step,st_));

          st_ = decr(st,i);
          if(passed[st_]>step) pq.push(make_pair(-step,st_));
        }
      }
    }
    return -1;
  }
};