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.

  • 3
    is that your homework ? – c69 Dec 23 '14 at 20:00
  • 1
    @c69 No! It's part of a bigger problem that I should solve for my work – AshKan Dec 23 '14 at 20:17
  • 7
    @AshKan - not your fault, but you'd be amazed how many homework assignments get cut & pasted in here with little or no thought. We usually ask them to read Open letter to students with homework so they understand why they need to think the problem through for themselves. Since yours is not a homework problem, perhaps you could elaborate with a sample matrix or two and possibly explain how this fits into the bigger problem (so we're not facing an XY problem) – Dan Pichelman Dec 23 '14 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.