naoya_t@topcoder

SRM222 Div1 Medium: WalkingHome

過去問, 練習, Tutorials | 18:40 |

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

• BFSの例
• そんなに難しくない
• 最初のsubmit: 262.33points (34'29'')
• 南北の道を横断している途中に東西の道を縦断できてしまうバグでfailed
• 直したはず (#2のところ) が直ってなくてfailed
• １つ外の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;
  }
};