×

# DFSGRID-Editorial

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

Medium-Hard

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

This question is marked "community wiki".

255385251
accept rate: 0%

this problem is RAD ! KUDOS !

(20 Aug '13, 00:08)
1

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

(20 Aug '13, 01:49)

 2 Shouldn't the brown pattern in case sr=1 begin from the right side, not from the left? answered 19 Aug '13, 12:46 6★jevi 61●4 accept rate: 0% Yep, you are right. Sorry for the mistake, fixed now. (19 Aug '13, 13:18) Another thing is that I think it should be called sc=1, not sr=1. (19 Aug '13, 19:12) thanks again. Will try to avoid such mistakes in future. (19 Aug '13, 19:54) why tthe images destroying this essence of editorial............... (20 Aug '13, 10:36)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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:

×15,482
×1,237
×921
×816
×8
×1

question asked: 19 Aug '13, 00:55

question was seen: 2,332 times

last updated: 20 Aug '13, 10:36