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

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



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


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

Setter’s solution
Tester’s Solution
Editorialist’s Solution


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


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…