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.