P1913 Combat Paratroopers of Country L

Country L is about to go to war with Country I! To infiltrate the enemy country, the commander decides to send paratroopers into the enemy! However, the wind in the enemy country is so strong that it can make paratroopers circle around at the same altitude until they are blown into a windless area... (poor soldiers).

The territory of Country I is an $n \times m$ rectangle, and each cell has its own wind direction. When a paratrooper is at some cell, according to the wind direction descriptor on that cell, the following will happen: |Wind descriptor|What happens| |:-:|:-:| |`u`|The paratrooper moves up by one cell.| |`d`|The paratrooper moves down by one cell.| |`l`|The paratrooper moves left by one cell.| |`r`|The paratrooper moves right by one cell.| |`o`|The paratrooper lands successfully.| |`x`|The paratrooper fails to land.| We assume that all cells outside Country I’s territory have the wind descriptor `x`. Now, the commander drops one paratrooper on each of the $n \times m$ cells. How many paratroopers will eventually land successfully (that is, can reach a cell with descriptor `o` after a finite number of moves)?

The first line contains two positive integers $n, m\ (1 \leq n, m \leq 1000)$. The next $n$ lines each contain $m$ characters, representing the wind descriptor of each cell. It is guaranteed that only `u/d/l/r/o` appear in the input; `x` does not appear.

A single integer: the number of paratroopers that can land successfully.

Explanation of the sample: The $5$ paratroopers dropped in the first row will eventually move outside Country I’s territory, thus failing to land. The one paratrooper dropped in the second row, fifth column will do the same. The remaining $5 \times 5-5-1=19$ paratroopers will all land successfully. Translated by ChatGPT 5