naoya_t@topcoder

SRM456 Easy: SilverDistance

きょうの復習, 過去問 | 20:46 |

• 45度傾けたら超簡単だった
• 格子点以外への行き方が１通りしかない
• マンハッタン距離 + 格子点でなければ+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