Billy, a 7-year-old kid, is let loose in a park, which is an N-by-N grid of cells (x,y)[N][N]. His starting location is the Southwest corner (x,y) = (1, 1). He takes a walk in the park, always moving from a square to an adjacent square in one of the four cardinal directions. He never leaves the park, and never visits the same square twice. Eventually he ends up napping somewhere in the park.We are given the N-by-N matrix A, whose entries are

A[i,j] = * if Billy never visits cell(i,j),

A[i,j] = if Billy visited cell (i,j) and departed upwards (North direction);

A[i,j] = if Billy visited cell (i,j) and departed in the leftwards direction;

...similarly for,;

A[i,j] = BILLY if Billy is napping in cell (i,j).

As one example, A[1, 1] will contain an arrow indicating the first step Billy took after entering the park (unless he stopped to nap immediately). Describe an algorithm (in pseudo code) that makes only O(N) queries to the matrix A, and locates Billy. Partial credit for O(NlogN).

Prove the algorithm is correct and runs in O(N) time.