The final state looks like <<..<==..=>>..>, where = denotes a square that does not change from the initial state, < denotes a square replaced with a left-pointing footprint, and > denotes a square replaced with a right-pointing footprint. That is, the squares to the left of a square replaced with < will also be replaced with <, and the squares to the right of a square replaced with > will also be replaced with >. Additionally, only a maximal segment not containing . in the initial state can become the segment of =s. Therefore, there are only \(k+1\) possible final states, where \(k\) is the number of squares with a hole. The problem can be solved by finding the probability that each final state is realized.

Consider the number of sequences of operations that replace the leftmost \(d\) .s in the initial state with <s, and the remaining \(k-d\) . with >s. The operations on the \(d\) .s to the left and those on the \(t-d\) .s to the right do not affect each other. Thus, if we find the number \(L_d\) of desirable sequences of operations on the left side, and the number \(R_{t-d}\) of desirable sequences of operations on the right side, the sought number is \(L_dR_{t-d} \binom{k}{d}\).

To find \(L_0, \dots, L_k\), let us ignore the squares that are not eventually replaced with <s for now. We focus on the direction Snuke faces after filling the \(i\)-th square. If there are holey squares to the right of the \(i\)-th square when filling the \(i\)-th square, Snuke’s direction here does not affect the final state. The same goes for the square with a footprint in the initial state. This is because the \(i\)-th square will also become < when the holey square immediately to the right becomes <. On the other hand, if there is no holey square to the right of the \(i\)-th square, Snuke must face to the left.

Let us use this observation to create a recurrence formula on \(L_0,\dots,L_k\). Assume that \(d+1\) .s will get replaced with <s, and classify the cases according to when the leftmost holey square gets filled. If the leftmost one is the \((d+1)\)-th square to be filled, Snuke must face to the left; otherwise, he may face either direction. There are \(L_d\) ways to decide the relative order of the \(d\) remaining empty squares and Snuke’s directions on them, so we have \(L_{d+1}=(2d-1)L_d\).

Additionally, by swapping left and right in the operation, we can see that \(L_d = R_d\).

Sample Implementation in C++