(Right click on the image and select "View image" to view a larger version.)
A path in the picture above is defined as a sequence of cells such that:
- It begins on the leftmost white cell and ends on the rightmost white cell.
- It only uses white cells.
- Any two consecutive cells in the path are orthogonally adjacent (share a side).
- Any two orthogonally adjacent cells appear consecutive in at most one position. (Essentially this means the path doesn't cross any side of any square more than once.) Note that a path may use a square more than once, only that it may not cross a side more than once.
If you're familiar with Path counting, this is pretty much the same definition of path as used in that problem, only made more formal.
In fact, the question is the same. Compute the number of possible paths in the picture above.