mayoko’s diary

プロコンとかいろいろ。

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];
    }
};