# Problem Link:

Practice

Contest

**author**: Tasnim Imran Sunny

**tester**: Roman Rubanenko

**editorialist**: Utkarsh Lath

# Difficulty:

Medium-Hard

# Pre-requisites:

ad-hoc

# 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 (R-sr).

- For the case when parity of
**R-sr** 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 tc-rc+1 // target to the immediate right of source
if sr < tr
if tc == C // target below source in last column
return (C-tc+1) + (tr-sr) // horizontal distance + vertical distance

return (C-sc+1) + (R-sr) + pattern1(C-1, R-tr, C-1-tc)

int inc = C - sc + 1 + C * (R-sr) // from DFS of part below source
if (R-cr) is even
if sr==tr // immediately to left of source
return inc + sc-tc
return inc + sc-1 + pattern1(C, sr-tr-1, tc-1) // 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 y-coordinate(0 based), right is x co-ordinate(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 = C-sc+1 + C * (R-sr); // from DFS of part below source
if (R-sr)%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 (r-1,1) from (r, i) for some row r.
if(tc-tr < Oc-Or) // 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 Or-tr is odd // approaching "end of round"

if tr == 1 // special handling for case in image 2 above
return inc - C-1 + Oc-Or + tr-tc
return inc - (tc-1)) // distance from "end of round" is tc-1

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 Or-boundaryRow is odd // case in image 3 above
boundaryRow ++

if tr < boundaryRow // outside boundary, apply pattern1
return pattern1(C, thresh-tr-1, tc-1) + C * (Or-boundaryRow) +Oc - 1

int rounds = (Or-tr-1) / 2
int inc = rounds * 2 * (C + 1)

if Or-tr 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.

Setter's solution

Tester's Solution

Editorialist's Solution

asked
**19 Aug '13, 00:55**

5★utkarsh_lath ♦♦

255●38●52●51

accept rate:
0%

this problem is RAD ! KUDOS !

boom question....really touch to crack in short contest