BOJ 11111 두부장수 장홍준 2

void solve(){
    int N, M; cin >> N >> M;

    vector<vector<int>> costs = {
        {10, 8, 7, 5, 1},
        {8, 6, 4, 3, 1},
        {7, 4, 3, 2, 1},
        {5, 3, 2, 2, 1},
        {1, 1, 1, 1, 0}
    };

    vector<vector<int>> board(N, vector<int>(M));
    map<char, int> mp;
    mp['A'] = 0; mp['B'] = 1; mp['C'] = 2; mp['D'] = 3; mp['F'] = 4;
    rep(i, 0, N){
        string S; cin >> S;
        rep(j, 0, M) board[i][j] = mp[S[j]];
    }

    MinCostMaxFlow MCMF(N*M+2);
    MCMF.setST(N*M, N*M+1);
    vector<int> dx = {-1, 1, 0, 0}, dy = {0, 0, -1, 1};
    rep(i, 0, N) rep(j, 0, M){
        if((i+j)%2){
            MCMF.add(i*M+j, N*M+1, 1, 0);
            continue;
        }

        MCMF.add(N*M, i*M+j, 1, 0);
        rep(d, 0, 4){
            int nx = i + dx[d], ny = j + dy[d];
            if(nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
            MCMF.add(i*M + j, nx*M + ny, 1, -costs[board[i][j]][board[nx][ny]]);
        }
    }
    cout << max(0LL, -MCMF.match());
}