Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-05-17

SRM222 Div1 Medium: WalkingHome

| 18:40 | SRM222 Div1 Medium: WalkingHome - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM222 Div1 Medium: WalkingHome - naoya_t@topcoder SRM222 Div1 Medium: WalkingHome - naoya_t@topcoder のブックマークコメント

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

  • BFSの例
  • そんなに難しくない
  • 最初のsubmit: 262.33points (34'29'')
  • 南北の道を横断している途中に東西の道を縦断できてしまうバグでfailed
  • 直したはず (#2のところ) が直ってなくてfailed
  • 1つ外のifで分岐させてやっと直った。
    • 横断している道から横にそれたら斜め横断になってしまうということ
  • 教訓:きちんと場合分けしてテストしよう
#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 WalkingHome {
 public:
  int fewestCrossings(vector <string> m) {
    int w=sz(m[0]),h=sz(m);
    int start_x=-1, start_y=-1, goal_x=-1, goal_y=-1;
    vector<vector<bool> > fu(h);
    rep(y,h) { fu[y].resize(w); rep(x,w) fu[y][x]=true; }
    rep(y,h) rep(x,w) {
      switch(m[y][x]){
        case 'S': start_x=x; start_y=y; break;
        case 'H': goal_x=x; goal_y=y; break;
        case '*':
        case 'F': fu[y][x] = false; break;
        case '|': case '-':
        case '.':
          break;
      }
    }
    priority_queue<pair<int,pair<int,int> > > pq;
    pq.push(make_pair(0,make_pair(start_x,start_y)));
    while(!pq.empty()){
      int sc=-pq.top().first;
      int x=pq.top().second.first, y=pq.top().second.second;
      if (x==goal_x && y==goal_y) return sc;
      pq.pop();
      if(fu[y][x]){
        int cur = m[y][x];
        if (0<=x-1 && cur!='-') { // <
          if (fu[y][x-1]) {
            int nxt=m[y][x-1], nsc=sc;
            switch(nxt){
              case '-': case '*': case 'S': case 'F': break;
              case '|':
                //if (cur=='-') break; // #2
                if (cur!='|') nsc++; //thru
              case '.': case 'H':
                pq.push(make_pair(-nsc,make_pair(x-1,y)));
                break;
            }
          }
        }
        if (x+1<=w-1 && cur!='-') { // >
          if (fu[y][x+1]) {
            int nxt=m[y][x+1], nsc=sc;
            switch(nxt){
              case '-': case '*': case 'S': case 'F': break;
              case '|':
                //if (cur=='-') break; // #2
                if (cur!='|') nsc++; //thru
              case '.': case 'H':
                pq.push(make_pair(-nsc,make_pair(x+1,y)));
                break;
            }
          }
        }
        
        if (0<=y-1 && cur!='|') { // ^
          if (fu[y-1][x]) {
            int nxt=m[y-1][x], nsc=sc;
            switch(nxt){
              case '|': case '*': case 'S': case 'F': break;
              case '-':
                //if (cur=='|') break; // #2
                if (cur!='-') nsc++; //thru
              case '.': case 'H':
                pq.push(make_pair(-nsc,make_pair(x,y-1)));
                break;
            }
          }
        }
        if (y+1<=h-1 && cur!='|') { // v
          if (fu[y+1][x]) {
            int nxt=m[y+1][x], nsc=sc;
            switch(nxt){
              case '|': case '*': case 'S': case 'F': break;
              case '-':
                //if (cur=='|') break; // #2
                if (cur!='-') nsc++; //thru
              case '.': case 'H':
                pq.push(make_pair(-nsc,make_pair(x,y+1)));
                break;
            }
          }
        }
      }
      fu[y][x] = false;
    }
    return -1;
  }
};
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090517