Algorithm for grid with obstacles and movement restriction

Question

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.

Answer 1

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.

Answer 2

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