DFSGRID-Editorial

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.

image cant be displayed

  • 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

3 Likes

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

2 Likes

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

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

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

this problem is RAD ! KUDOS !

boom question…really touch to crack in short contest

1 Like

why tthe images destroying this essence of editorial…

//