You are not logged in. Please login at to post your questions!



Problem Link:


author: Tasnim Imran Sunny
tester: Roman Rubanenko
editorialist: Utkarsh Lath






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).


In the most general case, the algorithm will proceed in one of the following ways depending on parity of (R-sr).

image cant be displayed image cant be displayed

  • 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 image cant be displayed 2 image cant be displayed

3 image cant be displayed 4 image cant be displayed

//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.

image cant be displayed

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

image cant be displayed

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

image cant be displayed

  • R=1 or C=1
    Can be handled as a special case.

image cant be displayed


Tester's solution is a bit untidy. Editorialist's solution is based on above ideas.

Setter's solution
Tester's Solution
Editorialist's Solution

This question is marked "community wiki".

asked 19 Aug '13, 00:55

utkarsh_lath's gravatar image

5★utkarsh_lath ♦♦
accept rate: 0%

edited 19 Aug '13, 20:02

this problem is RAD ! KUDOS !

(20 Aug '13, 00:08) aichemzee4★

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

(20 Aug '13, 01:49) akashverma_1233★

Shouldn't the brown pattern in case sr=1 begin from the right side, not from the left?


answered 19 Aug '13, 12:46

jevi's gravatar image

accept rate: 0%

Yep, you are right. Sorry for the mistake, fixed now.

(19 Aug '13, 13:18) utkarsh_lath ♦♦5★

Another thing is that I think it should be called sc=1, not sr=1.

(19 Aug '13, 19:12) kevinsogo7★

thanks again. Will try to avoid such mistakes in future.

(19 Aug '13, 19:54) utkarsh_lath ♦♦5★

why tthe images destroying this essence of editorial...............

(20 Aug '13, 10:36) akashverma_1233★
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:


question asked: 19 Aug '13, 00:55

question was seen: 2,332 times

last updated: 20 Aug '13, 10:36