There are only two approaches to reach a square in two moves or less:

• Move downward, and then move right

• Move right, and then move downward

(Moving zero squares is allowed in each of the moves above). Since we can reach some of the squares in both approaches, we have to be careful not to count those squares twice.

We can find the squares reachable in the latter approach in a total of \(O(M+W)\) time by finding the uppermost obstacle in each column.

The former can be found in the similar way; but this time, we have to count only those that cannot be reached by the latter approach. A square is reachable only by the latter approach if and only if there is an obstacle above (we regard that every square to the right of the leftmost obstacle in the first row has an obstacle as well).

Therefore, for each row, we can manage if each column had an obstacle so far with a Segment Tree or a Binary Indexed Tree, so that we can calculate the answer in a total of \(O((H+W) \log W)\) time.