Smoky Salmon
本题没有可用的提交语言。
Description
Chef Maxine is in a busy $N$ by $M$ kitchen trying to cook up some salmon for the night's dinner rush. Due to the busy night, the kitchen has become filled with smoke. Maxine has to keep running back and forth to the refrigerator to get more fresh salmon and is getting exhausted. She must navigate around various obstacles in the kitchen to get to the fridge and grab more salmon in the way that will leave her least exhausted.
While normally walking through a tile adds $1$ to her exhaustion, walking through the smoke makes it harder to breathe, so it adds to her exhaustion by $3$. Specifically, she gets more exhausted if there is smoke on the tile as she is leaving it. The smoke appears to take on a repeating pattern of size $N$ by $K$ and drifts left by one every time step. This means at the start the first column of smoke is over the first column of the map, continuing to the right and cutting off/repeating as necessary to cover the map. At the second time step, the second column of smoke is over the first column of the map, still continuing and cutting off/repeating as necessary. This continues, with a new column of smoke appearing above the rightmost column of the map at each timestep.
At each timestep, Chef Maxine must either walk up, down, left, right, as long as there are no obstacles at this square. She always avoids staying still so it doesn't look like she's wasting time. Chef Maxine wants to know what the least exhausted she could possibly be by the time she reaches the fridge.
The first line will consist of $3$ integers $N, M, K$ $(1 \leq N, M, K \leq 100)$ where $N$ is the number of rows in both the kitchen and the smoke pattern.
The following $N$ rows will each consist of $M$ characters defining the layout of the kitchen. A '#' represents an obstacle, '.' represents free space, 'C' indicates the starting position of the chef, and 'R' represents the location of the refrigerator.
The following $N$ rows will each consist of $K$ characters defining the repeating pattern of the smoke. A '1' indicates there is smoke in this location and a '0' indicates there is not.
Note: It is guaranteed there exists at least some path from 'C' to 'R' in the kitchen.
Your output should consist of a single integer indicating the least exhausted Chef Maxine could be by the time she reaches the fridge.
Input
The first line will consist of $3$ integers $N, M, K$ $(1 \leq N, M, K \leq 100)$ where $N$ is the number of rows in both the kitchen and the smoke pattern.
The following $N$ rows will each consist of $M$ characters defining the layout of the kitchen. A '#' represents an obstacle, '.' represents free space, 'C' indicates the starting position of the chef, and 'R' represents the location of the refrigerator.
The following $N$ rows will each consist of $K$ characters defining the repeating pattern of the smoke. A '1' indicates there is smoke in this location and a '0' indicates there is not.
Note: It is guaranteed there exists at least some path from 'C' to 'R' in the kitchen.
Output
Your output should consist of a single integer indicating the least exhausted Chef Maxine could be by the time she reaches the fridge.
3 3 4
C.#
...
..R
0101
1010
1111
3 3 2
C.#
...
#.R
01
01
01
1 3 4
C.R
1001
4
6
4
Note
Sample 1:
We start at C. We move over to the right which adds 1 to our exhaustion since there was no smoke on C. We then move down which adds 1 to our exhaustion. We move right again and then finally move down. None of these moves caused us to leave a square with smoke in it, so we get a total exhaustion of 4.
Sample 2:
We start at the C. We move over to the right, adding 1 exhaustion. There is still no smoke in the current tile, so we go down adding another 1. Now there is smoke in this tile, so when we move down again it adds 3. Finally, there is no smoke so we move right to the R which adds 1 to our exhaustion for a total of 6.