Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-12-23

SRM456 Easy: SilverDistance

| 20:46 | SRM456 Easy: SilverDistance - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM456 Easy: SilverDistance - naoya_t@topcoder SRM456 Easy: SilverDistance - naoya_t@topcoder のブックマークコメント

  • 45度傾けたら超簡単だった
  • 格子点以外への行き方が1通りしかない
  • マンハッタン距離 + 格子点でなければ+1
class SilverDistance {
 public:
  int minSteps(int sx, int sy, int gx, int gy) {
    int dx = gx-sx, dy = gy-sy;
    if (dx==0&&dy==0) return 0;
    int up=0;
    int ex =  dx+dy;
    int ey = -dx+dy;
    if (ex&1) {
      up=1; ex--; ey--;
    }
    int hx = ex/2, hy = ey/2;
    return abs(hx)+abs(hy)+up;
  }
};

こんな問題で悩むなんて… orz

rng_58rng_582009/12/24 19:36C = 2 のとき、奇数なら1を足す関数
f(x) = x + ((x%2 == 0) ? 0 : 1)
とかが条件を満たします

n4_tn4_t2009/12/25 11:49問題作成者様直々にコメントありがとうございます!!
なるほどそういうのもアリですね。頭固かったです。

トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20091223