The minimum number of segments required to draw X’s is equal to the following value.

• The number of integer pairs \((i,j)\) such that square \((i,j)\) has an X but square \((i-1,j-1)\) doesn’t, plus the number of integer pairs \((k,l)\) such that square \((k,l)\) has an X but square \((k-1,l+1)\) doesn’t (where if square \((i-1,j-1)\) or \((k-1,l+1)\) does not exist, then we regard that they do not have an X in it)

Therefore, this problem can be represented as follows.

For each square, choose one of the two states: to draw an X or not to draw. If you do draw an X to square \((i,j)\), then you earn a score \(A_{i,j}\); if you don’t, you obtain no score.

On the other hand, for each of integer pairs \((i,j)\) such that square \((i,j)\) has an X but square \((i-1,j-1)\) doesn’t, and for each of integer pairs \((k,l)\) such that square \((k,l)\) has an X but square \((k-1,l+1)\) doesn’t, a score \(C\) is subtracted.

Maximize the score you obtain.

This does not look so good, since there are both additions and subtractions in it. Let us express it only with additions:

For each square, choose one of the two states: to draw an X or not to draw. If you don’t draw an X to square \((i,j)\), then you are imposed a cost \(A_{i,j}\); if you do, you are imposed no cost.

On the other hand, for each of integer pairs \((i,j)\) such that square \((i,j)\) has an X but square \((i-1,j-1)\) doesn’t, and for each of integer pairs \((k,l)\) such that square \((k,l)\) has an X but square \((k-1,l+1)\) doesn’t, a cost \(C\) is accumulated.

Maximize the sum of \(A_{i,j}\), subtracted by the cost. In other words, minimize the sum of cost.

Now it is quite easy to handle with. This cost minimization problem can be boiled down to a minimum cut problem for the two vertices, the initial vertex and the terminal vertex, on the graph constructed as follows:

1. Prepare a graph with \(H \times W\) vertices and \(0\) edges, where each vertex correspond to each square of the grid. Additionally, add two vertices, the initial and the terminal, to the graph
2. For every square \((i,j)\), add an edge described as follows:
   • A directed edge from the initial to square \((i,j)\) with weight \(A_{i,j}\)
3. For every square \((i,j)\) such that square \((i-1,j-1)\) does not exist, add an edge described as follows:
   • A directed edge from square \((i,j)\) to the terminal with weight \(C\)
4. For every square \((i,j)\) such that square \((i-1,j-1)\) exists, add two edges described as follows:
   • A directed edge from square \((i,j)\) to the terminal with weight \(0\)
   • A directed edge from square \((i,j)\) to square \((i-1,j-1)\) with weight \(C\)
5. For every square \((i,j)\) such that square \((i-1,j+1)\) does not exist, add an edge described as follows:
   • A directed edge from square \((i,j)\) to the terminal with weight \(C\)
6. For every square \((i,j)\) such that square \((i-1,j+1)\) exists, add two edges described as follows:
   • A directed edge from square \((i,j)\) to the terminal with weight \(0\)
   • A directed edge from square \((i,j)\) to square \((i-1,j+1)\) with weight \(C\)

You may just code this graph.

With Dinic’s algorithm, the complexity is \(O(HW \sqrt{HW})\).

There was a mistake in the complexity analysis. Since the complexity of Dinic’s algorithm is \(O(EV^2)\) where \(V\) and \(E\) are the number of edges and vertices of the graph, it should be \(O(H^3W^3)\). Alternatively, if every \(A_{i,j}\) and \(C\) are at most \(K\), the complexity is \(O(KHW \sqrt{HW})\). We should have set the constraints small enough so that we could prove this solution would work. We apologize for that.

In C++, it is very useful to use atcoder library.

Sample code (C++)

#include<bits/stdc++.h>
#include<atcoder/maxflow>
using namespace std;
using namespace atcoder;

#define rep(i, j, n) for(int i = int(j); i < int(n); i++)

using ll = long long;

int main(){
    int H,W,C; cin >> H >> W >> C;
    mf_graph<ll> graph(H*W+2);
    vector<vector<int>> A(H,vector<int>(W));
    rep(i,0,H){
        rep(j,0,W) cin >> A[i][j];
    }
    int sz = H*W;
    rep(i,0,H){
        rep(j,0,W){
            int now = i*W+j;
            graph.add_edge(sz,now,A[i][j]);
        }
    }
    rep(i,0,H){
        rep(j,0,W){
            int now = i*W+j;
            if(0 < i && 0 < j){
                int next = (i-1)*W+(j-1);
                graph.add_edge(now,sz+1,0);
                graph.add_edge(now,next,C);
            }
            else{
                graph.add_edge(now,sz+1,C);
            }
        }
    }
    rep(i,0,H){
        rep(j,0,W){
            int now = i*W+j;
            if(0 < i && j+1 < W){
                int next = (i-1)*W+(j+1);
                graph.add_edge(now,sz+1,0);
                graph.add_edge(now,next,C);
            }
            else{
                graph.add_edge(now,sz+1,C);
            }
        }
    }
    ll ans = 0;
    rep(i,0,H){
        rep(j,0,W) ans += A[i][j];
    }
    ans -= graph.flow(sz,sz+1);
    cout << ans << endl;
}