Submission #16752194

---

Source Code Expand

#include <iostream>
#include <atcoder/mincostflow>

using namespace std;
using namespace atcoder;

int main() {
    int n, m;
    cin >> n >> m;

    vector<string> board(n);
    for (int i = 0; i < n; i++) {
        cin >> board[i];
    }

    mcf_graph<int, int> g(n * m + 2);
    int sv = n * m, tv = sv + 1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (board[i][j] == '#') continue;
            g.add_edge(i * m + j, tv, 1, 10000 - i - j);
            if (board[i][j] == 'o') {
                g.add_edge(sv, i * m + j, 1, i + j);
            }
            if (i) {
                g.add_edge((i - 1) * m + j, i * m + j, 10000, 0);
            }
            if (j) {
                g.add_edge(i * m + (j - 1), i * m + j, 10000, 0);
            }
        }
    }

    auto answer = g.flow(sv, tv);

    cout << answer.first * 10000 - answer.second << endl;
    return 0;
}

Submission Info

Judge Result