Given a matrix A with 0 and 1 entries. Neighbours of a[i,j] are a[i-1,j], a[i+1,j], a[i,j-1] and a[i,j+1] (if exists any).Tow neigbour entries are an Improper pair if they have not equal values.if number of improper pair of matrix A equals to q, then the penalty of matrix will be equals to b*q (which b is a natural number).Before computing the penalty, we can inverse some of entries (0 -> 1 or 1 -> 0) with cost of a (for each entry inversion). The goal is minimizing the sum of inversion cost and final penalty; An algorithm (with help of network flow) should be proposed for this goal.My Idea for start:I assume each entry a node, then create a node s, and connect it to all 0 entries.Then create a node t, and connect all 1 entries to it.
Design an algorithm with network flow
algorithms