Box pushing robot

A factory moves a heavy box with a robot. To move the box in some direction, the robot first has to reach the cell behind the box, then push the box forward in that direction.

The factory floor is an $m \times n$ grid. A cell that holds an obstacle is blocked. The robot and the box each occupy one cell. In the figure on the right, blocked cells are gray, and r and s mark the robot and the box.

A cell is free if it is not blocked and the box is not on it. In one step the robot moves from its current cell to the cell above, below, to the left, or to the right of it, provided that cell is free. If the neighboring cell holds the box, the robot can push the box one cell in the same direction, provided the cell the box enters is free. The robot and the box can never leave the grid.

The box starts at cell s and the robot at cell r. Cell t is reachable from s if some sequence of robot steps pushes the box from s to t. In the figure, the left cell marked t is reachable from s, while the cell marked t' is not. Given the grid and the two starting positions, count how many cells are reachable from s. The cell s itself always counts, even when the robot can never reach the box.

The input holds several test cases. The first line of a test case has two integers m and n ($1 \le m, n \le 1000$), the number of rows and the number of columns of the grid. Each of the next m lines has a string of length n, where the j-th character of the i-th line is cell (i, j). An obstacle is o, the robot is r, the starting cell of the box is s, and every other cell is -. Each grid has exactly one r and exactly one s. The last line of the input is 0 0 and is not a test case. The sum of $m \times n$ over all test cases is at most $10^6$.

For each test case, print one line with the number of grid cells the box can reach from its starting cell s.