Problem Link:
author: Tasnim Imran Sunny
tester: Roman Rubanenko
editorialist: Utkarsh Lath
Difficulty:
MediumHard
Prerequisites:
adhoc
Problem:
The chef has written DFS traversal algorithm for R * C grid. He starts at (sr, sc) and terminates when he reaches (tc, tr). His algorithm looks for empty adjacent cells in the following order: right, down, left, up. You find need to find how many vertices he traverses before hitting (tc, tr).
Explanation:
In the most general case, the algorithm will proceed in one of the following ways depending on parity of (Rsr).
 For the case when parity of Rsr is even is easy to handle(refer to image on left), because the resulting pattern is very simple.
if sr == tr and sc >= tc
return tcrc+1 // target to the immediate right of source
if sr < tr
if tc == C // target below source in last column
return (Ctc+1) + (trsr) // horizontal distance + vertical distance
return (Csc+1) + (Rsr) + pattern1(C1, Rtr, C1tc)
int inc = C  sc + 1 + C * (Rsr) // from DFS of part below source
if (Rcr) is even
if sr==tr // immediately to left of source
return inc + sctc
return inc + sc1 + pattern1(C, srtr1, tc1) // above source
int pattern1(int cols, int top, int right) {
/ * solve for pattern
.
.
^<<
>>^
^<<
>>^
assuming you enter from bottom left, and move along direction suggested by arrows.
cols is number of columns
top is ycoordinate(0 based), right is x coordinate(0 based) * /
int res = cols * (top/2) * 2;
if top is odd
return res + (cols * 2)  right; // encountered when going from right to left
return res + right+1; // encountered when going from left to right
}
 In the other case(refer to image on right), the pattern is more interesting. It can end in one of the following ways.
1
2
3
4
//handling of cases when **sr == tr and sc >= tc** or **sr < tr** will remain same because the part for the pattern is same
int inc = Csc+1 + C * (Rsr); // from DFS of part below source
if (Rsr)%2 == 1
return inc + pattern2(sr, sc)
int pattern2(ll Or, ll Oc) {
/* solve for pattern
.
.
>^v<<<
^<>>^
>^v<<<
^<>>^
>^xxxxxxxxxxxxx
assuming you enter from bottom left and move along direction suggested by arrows.
Or(Obstacle row) is row of entrance(bottommost row in figure)
Oc(Obstacle column) is column of leftmost 'x'
* /
// a new "round" begins(and previous round ends) when search reaches (r1,1) from (r, i) for some row r.
if(tctr < OcOr) // on left side of the diagonal line ending at (Or, Oc)
int rounds = (Or  tr + 1) / 2
// no of "rounds" when it next changes direction.
int inc = (C+1) * 2 * rounds // 2 * (C+1) cells are seen in each round
if Ortr is odd // approaching "end of round"
if tr == 1 // special handling for case in image 2 above
return inc  C1 + OcOr + trtc
return inc  (tc1)) // distance from "end of round" is tc1
return inc+tc // passed "end of round"
// on right side of diagonal line
int boundaryRow = Or  Oc + 1 // topmost row beyond which pattern2 disappears
if OrboundaryRow is odd // case in image 3 above
boundaryRow ++
if tr < boundaryRow // outside boundary, apply pattern1
return pattern1(C, threshtr1, tc1) + C * (OrboundaryRow) +Oc  1
int rounds = (Ortr1) / 2
int inc = rounds * 2 * (C + 1)
if Ortr is odd // going rightwards, away from previous "end of round"
return inc + 1 + tc
return inc + 2 * (C + 1)  tc // going leftwards, towards next "end of round"
}
Apart from this, there are 4 special cases to be handled:

sc = 1
The order in which rows below source are traversed does not change. The rows above source are traversed by pattern1, and can be handled as a special case.

sr=R
The vertices are traversed in pattern2, and can be handled as a special case.

(sr, sc)=(R, C)
The vertices are traversed in pattern1, and can be handled as a special case.

R=1 or C=1
Can be handled as a special case.
Solutions:
Tester’s solution is a bit untidy. Editorialist’s solution is based on above ideas.