Matrix Balls [CSAcademy #71 B]

https://csacademy.com/contest/round-71/task/matrix-balls/

縦N横Mの行列がある。
各要素には別々な数が入っている。
最初、全ての行列に玉が1つ入っている。
隣接する8要素の中で自分よりも数が小さい要素に玉が移動する。
複数ある場合は一番小さい数の要素に移動する。
最終的に各要素に入っている玉の数は何個か。

解法

シミュレーションする。
最初に1つずつ玉をいれる。
　
次に玉の移動をシミュレーションするが、数が大きい要素から移動させていく。
そうしないと、移動させた後に、また、移動させるべき玉が入ってくる可能性があるためである。
数が大きい要素から隣接する要素に玉を移動させて、答える。

int H, W, A[505][505], ans[505][505];
int dx[8] = { 0,1,1,1,0,-1,-1,-1 };
int dy[8] = { -1,-1,0,1,1,1,0,-1 };
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> H >> W;
    rep(y, 0, H) rep(x, 0, W) cin >> A[y][x];

    rep(y, 0, H) rep(x, 0, W) ans[y][x] = 1;
    vector<pair<int, int>> v;
    rep(y, 0, H) rep(x, 0, W) v.push_back({ A[y][x], y * 505 + x });
    sort(all(v), greater<pair<int, int>>());

    fore(p, v) {
        int x = p.second % 505;
        int y = p.second / 505;

        int go = -1, mi = inf;
        rep(i, 0, 8) {
            int xx = x + dx[i];
            int yy = y + dy[i];

            if (0 <= xx and xx < W and 0 <= yy and yy < H) if (A[yy][xx] < A[y][x]) {
                if (A[yy][xx] < mi) {
                    go = i;
                    mi = A[yy][xx];
                }

            }
        }

        if (0 <= go) {
            int xx = x + dx[go];
            int yy = y + dy[go];
            ans[yy][xx] += ans[y][x];
            ans[y][x] = 0;
        }
    }

    rep(y, 0, H) {
        rep(x, 0, W) {
            if (x) printf(" ");
            printf("%d", ans[y][x]);
        }
        printf("\n");
    }
}