Need help — Modelling into a flow problem.

Revision en1, by rupav, 2020-04-17 10:12:08

I am trying to solve 1214D by making the free and impassable cells as nodes, source as (1, 1) and sink as (n, m). And then joining only those edges for which flow is possible (between cell and its first right neighbor, if both free; cell and its first down neighbor, if both free) with capacity 1. Now finding the max flow in this problem should give me either 0, 1, 2, which should be the answer I thought originally. But this approach fails on a tc 44, i.e.

4 5

.....

....#

.....

..#..

(My code o/p is 2, but it should be 1, by blocking (3, 4) cell)

I realized why it is failing, but my question is how to model it then as a flow problem. A good alternate solution is https://mirror.codeforces.com/blog/entry/69563?#comment-541155 . But I would like to solve it as a flow problem. What should be the approach while solving these types of flow problems? Thanks.

Tags flow networks, maxflow

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English rupav 2020-04-17 10:12:08 1040 Initial revision (published)