rupav's blog

By rupav, history, 4 years ago, In English

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 . But I would like to solve it as a flow problem. What should be the approach while solving these types of flow problems? Thanks.

Full text and comments »

  • Vote: I like it
  • +8
  • Vote: I do not like it