'Max flow algorithm - Ford-Fulkerson's method

I know I shouldn't ask this sort of question, but I'm hopeless atm, I need some help...

I got this question for my assignment - there is a broad that has m by n grid of squares, and we are trying to cut the grid by two adjacent squares - either vertically or horizontally. However, some squares in the board cant be used as they are defective. so what's the maximum number of pieces we can cut?

I was thinking using Ford-Fulkerson's method - that converts each square into vertex, but cant really figure out what should I do next...

Can some one comes up with a hint?

Many Thanks

algorithmmethodsgraphbipartite


Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source

Related Questions