SRM 456 div1 easy: SilverDistance
こういうの苦手っす。
解法
近いところでどう動くのが最適かを調べるのは面倒なので, 銀がゴール付近に近づいたら, あとは幅優先探索でごまかす, という方針で解きます。
ゴール付近に近づくまでは, 斜めに動きます。
const int B = 15; const int DX[5] = {1, 0, -1, -1, 1}; const int DY[5] = {1, 1, 1, -1, -1}; int dist[2*B][2*B]; class SilverDistance { public: int minSteps(int sx, int sy, int gx, int gy) { int ans = 0; while (abs(gx-sx) > 10 || abs(gy-sy) > 10) { if (sx < gx) sx++; else sx--; if (sy < gy) sy++; else sy--; ans++; } if (abs(gx-sx) <= 10) { if (sy > gy) { while (sy-gy > 10) { sy--; if (sx < gx) sx++; else sx--; ans++; } } else { while (gy-sy > 10) { sy++; if (sx < gx) sx++; else if (sx > gx) sx--; ans++; } } } else { while (abs(sx-gx) > 10) { if (sx < gx) sx++; else sx--; if (sy >= gy) sy--; else sy++; ans++; } } int dx = gx-sx, dy = gy-sy; memset(dist, 0, sizeof(dist)); dist[B][B] = 0; queue<pii> que; que.push(pii(0, 0)); while (!que.empty()) { pii p = que.front(); que.pop(); int y = p.first, x = p.second; for (int k = 0; k < 5; k++) { int ny = y+DY[k], nx = x+DX[k]; if (nx <= -B || nx >= B || ny <= -B || ny >= B) continue; if (!dist[ny+B][nx+B] && !(ny==0&&nx==0)) { dist[ny+B][nx+B] = dist[y+B][x+B]+1; que.push(pii(ny, nx)); } } } return ans+dist[dy+B][dx+B]; } };