2
$\begingroup$

We are given an $n \times n$ grid with some of the squares darkened.

Our goal is to move from the bottom-left to the top-right corner with the following constraints:

1) We cannot step on a darkened square.

2) Each move must be up or to the right.

3) We cannot move in the same direction consecutively four times.

Design an algorithm that runs in $O(n^2)$ time and outputs the set of all squares that can be reached from the bottom-left corner.

My thoughts: We can convert the grid to a graph in $O(n^2)$: each square (darkened or not) becomes a node, and adjacent squares correspond to edges; each edge is directed either rightwards or upwards. We can then remove the nodes that correspond to darkened squares. At this point, we can BFS or DFS from the top-left node, but we must keep track of condition 3 somehow, with some sort of "cost" array.

Another idea is to "chop off" (this can be formalized) a triangle from the upper left and lower right, which are "too high" and "too right" respectively. But then, the existence of the darkened squares causes some additional squares to be unreachable.

Any help would be appreciated.

$\endgroup$
2
  • $\begingroup$ What constitutes the move: only one square at a time, or any number of squares as long as they are on the same line? Subsequently, is moving in the same direction means just moving in a straight line, or making four subsequent moves with the same rotation (i.e. "right" four times), where direction is relative to the direction of the last move (as if you were manipulating a game character). $\endgroup$
    – wvxvw
    Oct 9, 2015 at 7:48
  • $\begingroup$ A "move" is moving one square either upwards or rightwards. Moving in the same direction is making four moves with the same direction (so RRR is not allowed). The directions "up" and "right" are fixed, like "north" and "east". $\endgroup$
    – Pom Pom
    Oct 9, 2015 at 12:42

2 Answers 2

2
$\begingroup$

You can depict states of the graph as following: (grid_position,|consecutive_left|,|consecutive_up|) if you are at state ([2,3],3,0) then you have no other option but to go up to ([3,3],0,1)

so you have n^2 * 4 * 4=16*n^2 states=O(n^2) states. And you can also save some space by noticing that states such as ([x,y],2,1) are impossible.

$\endgroup$
2
$\begingroup$

Here's a version that's slightly more efficient than jjohn's answer, though only by constant factors.

The idea is that, instead of two kinds of move (up and right) with the annoying restriction that we can't move the same way four times consecutively, we'll have six kinds of move (up one, up two, up three, right one, right two, right three) and the restriction that moving up must be followed by moving right, and vice-versa. That means, you're forbidden from moving up one, then up one again but that's OK because you could have just moved up two as a single move.

To implement this, the state space is the set of triples $(x,y,d)$, where $(x,y)$ is the co-ordinates in the grid and $d\in\{\uparrow,\rightarrow\}$ is the direction of the previous move. We'll adopt the convention that the "previous move" from the initial position was $\uparrow$. The potential edges are as follows:

  • from $(1,1,\uparrow)$ to $(1,i,\uparrow)$ and $(i,1,\rightarrow)$ for each $i\in\{2,3,4\}$;

  • from $(x,y,\uparrow)$ to $(x+i,y,\rightarrow)$ for each $i\in\{1,2,3\}$;

  • from $(x,y,\rightarrow)$ to $(x,y+i,\uparrow)$ for each $i\in\{1,2,3\}$.

From this set of potential edges, delete any edge that starts at, ends at or "jumps over" a forbidden square and, of course, any edge that would take you off the board ($x>n$ or $y>n$). So far, our two goal states are $(n,n,\uparrow)$ and $(n,n,\rightarrow)$. Life would be very slightly easier if we only had one goal state, so redirect any edge that points to $(n,n,\rightarrow)$ so it points to $(n,n,\uparrow)$ instead.

Now, use your favourite $s$–$t$ connectivity algorithm to find if there's a path from $(1,1,\uparrow)$ to $(n,n,\uparrow)$. All of this can be done in quadratic time, since the only expensive part is building the graph.

If you care, you can be much more space-efficient by building the graph on the fly. Savitch's theorem says that you can solve $s$–$t$ connectivity on a graph with $n^2$ vertices in space $O((\log n^2)^2) = O((\log n)^2)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.