Milan cemetery P85166


Statement
 

pdf   zip

html

Legend has it that SWERC teams have a curse with cemeteries. This year, Xavier and Izan woke up the day before the competition in Milan’s cemetery. It was so monumental that they decided to visit everything. However, they didn’t want to get too tired.

The cemetery is an n × m grid, and they woke up in position (x, y). Can you help them figure out the minimum number of changes of direction needed to visit every cell? They can only move in the N, S, E, O directions.

For instance, to the right you can see the first case of the sample. It is possible to visit all the cells with only four changes of direction.


(4,3) unit=1.15, linewidth=0.8

linecolor=black

[fillcolor=green,fillstyle=solid](0,0)(4,0)(4,3)(0,3)

[linestyle=dotted](1,0)(1,3) [linestyle=dotted](2,0)(2,3) [linestyle=dotted](3,0)(3,3) [linestyle=dotted](0,1)(4,1) [linestyle=dotted](0,2)(4,2)

linewidth=2.4

[fillcolor=black,fillstyle=solid](2.5,1.5)0.07 ->(2.5,1.5)(0.55,1.5) ->(0.5,1.5)(0.5,2.45) ->(0.5,2.5)(3.45,2.5) ->(3.5,2.5)(3.5,0.55) ->(3.5,0.5)(0.5,0.5)

Input

Input consists of several cases, each one with n, m, x and y. Assume that both n and m are between 1 and 106, 1 ≤ x ≤ n, and 1 ≤ y ≤ m.

Output

For each case, print the minimum number of changes of direction required to visit the whole cemetery.

Public test cases

  • Input

    3 4 2 3
1 1 1 1
9 1 5 1

    Output

    4
0
1
    • Information
    Author
    Edgar Moreno
    Language
    English
    Official solutions
    C++
    User solutions
    C++