P4601 [HEOI2012] Wilderness Expedition

Xiao H is an explorer. He has left his footprints on Mount Everest, the vast African savanna, and the beautiful yet frigid Antarctic continent. This time, he heads to the Amazon rainforest in South America, a place full of venomous insects, ferocious beasts, and all kinds of legends. He spent a lot of time preparing for this exciting expedition. Once ready, Xiao H and his assistant, led by a local guide, stepped into the rainforest.

Using a GPS system, they obtained a rough map of the rainforest. The map is an $n$-by-$m$ character grid: '.' denotes empty ground, '*' denotes impassable terrain, '#' denotes an area that needs to be cleared, and 'H' marks Xiao H's position, which is also empty ground. There are $t$ types of movements, denoted by $a[i]$, $b[i]$ ($1 \leq i \leq t$). If they are currently at row $x$, column $y$, then their next position can be row $x + a[i]$, column $y + b[i]$, or the opposite direction, row $x - a[i]$, column $y - b[i]$. Each day, they may choose exactly one movement type and move a positive number of steps continuously in the forward or backward direction, then stop; they are not allowed to stay put. During that day’s movement, they may not enter any impassable cells ('*'). If they reach a cell marked '#', they stop moving immediately. For the rest of the day, they clear that cell; afterwards, it permanently becomes empty ground ('.'). They send you $q$ queries over the network, asking for the number of cells they can reach on day $d[i]$ ($1 \leq i \leq q$). It is guaranteed that there is no situation where they cannot move at all. Can you help them?

- The first line contains three positive integers $n$, $m$, and $t$. - Lines $2$ to $n+1$: each line contains $m$ characters (each is one of '.', '*', '#', 'H'; there is exactly one 'H'). - Lines $n+2$ to $n+t+1$: each line contains two integers $a[i]$ and $b[i]$ (not both $0$). - Line $n+t+2$: a single integer $q$. - Lines $n+t+3$ to $n+t+q+2$: each of the next $q$ lines contains one integer $d[i]$, the queried day.

Output $q$ lines. For each query, output the number of cells that can be reached on day $d[i]$.

Constraints: - For 20% of the testdata, $n, m \leq 4$, $q \leq 100$. - For 70% of the testdata, $n, m \leq 300$. - For 100% of the testdata, $n, m \leq 1000$, $t \leq 5$, $q \leq 1000$, $0 \leq d[i] \leq 10^9$. HEOI 2012 Day 2 Task 3. Translated by ChatGPT 5