IndeedなうB:D問題:Game on a Grid

本番何もわからずに通したけど,しっかりプリム法書いてて面白かった。

問題:D: Game on a Grid - Indeedなう（オープンコンテストB） | AtCoder

解法:すべてのマスが非負なので,点数を最大化するならとりあえずすべてのマスを通るのが良い。これで盤面に書いてある数の合計分の点数は確定。
この後は実は最大全域木を考えれば良いだけ(僕は最大全域木という単語よく知らなかったのですが,よく知られている最小全域木と同じアルゴリズムで求められます)。
一応詳しく説明します。まず盤面をグラフに解釈するために,互いに隣接しているセル(x,y)とセル(nx,ny)の辺の重みはP(x,y)*P(nx,ny)とします。すでに盤面の数分の点数は確定しているのであと最大化しないといけないのは,上で定義した辺の重みになります。しかし,がむしゃらにすべての辺を選んで良いのではありません。具体的には,選ぶ辺はループができてはいけません。なぜかというと,ループができたとすると,あるセルは2つの方向から点数を得ることになりますが,問題の条件的にそれをやってはいけないからです。また,セルはすべて連結するので木,特に全域木になります。この条件で辺の重みの合計を最大化するので,最大全域木を求めれば良いです。
以下ソースコード。プリム法で書いてます。初めて書いたのでわかりにくいかもですが。

const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
const int MAX = 110;
int H, W;
int sx, sy, gx, gy;
ll field[MAX][MAX];
bool done[MAX][MAX];

struct Point {
    int y;
    int x;
    Point() {}
    Point(int y, int x) : y(y), x(x) {}
    bool operator<(const Point& rhs) const {
        return y < rhs.y;
    }
};

int main(void) {
    cin >> H >> W;
    cin >> sx >> sy;
    cin >> gx >> gy;
    sx--; sy--; gx--; gy--;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> field[i][j];
        }
    }
    ll ans = field[sy][sx];
    done[sy][sx] = true;
    priority_queue<pair<int, Point> > que;
    for (int k = 0; k < 4; k++) {
        int y = sy+dy[k];
        int x = sx+dx[k];
        if (y < 0 || y >= H || x < 0 || x >= W) continue;
        que.push(make_pair(field[sy][sx] * field[y][x], Point(y, x)));
    }
    while (!que.empty()) {
        auto now = que.top(); que.pop();
        Point p = now.second;
        if (done[p.y][p.x]) continue;
        done[p.y][p.x] = true;
        ans += field[p.y][p.x] + now.first;
        for (int k = 0; k < 4; k++) {
            int ny = p.y+dy[k];
            int nx = p.x+dx[k];
            if (ny < 0 || ny >= H || nx < 0 || nx >= W) continue;
            que.push(make_pair(field[p.y][p.x] * field[ny][nx], Point(ny, nx)));
        }
    }
    cout << ans <<  endl;
    return 0;
}