P7904 Burning Clouds

A country road can be approximated as an $n\times m$ matrix. There are many kinds of road tiles; only a small part of them are listed here: 1. ``#``: Pond, impassable. 2. ``|``: Straight-type road. In the vertical direction you can only go straight; in the horizontal direction you can only turn left or right. 3. ``-``: Straight-type road. In the horizontal direction you can only go straight; in the vertical direction you can only turn left or right. 4. ``/``: Turning-type road. In the vertical direction you can only turn right; in the horizontal direction you can only turn left. 5. ``\``: Turning-type road. In the vertical direction you can only turn left; in the horizontal direction you can only turn right. 6. ``.``: Four-way intersection. You can go straight, turn left, or turn right. 7. ``S``: Entrance. Entering this tile from outside the countryside takes no time. 8. ``E``: Exit. Leaving the countryside from this tile takes no time. Forward-type road: After reaching this cell, the direction must spend time to turn to `?`. If the incoming direction is already `?`, then it costs no time and you must jump one cell. 9. ````: `? = East`. 11. ``^``: `? = North`. 12. `v`: `? = South`. **In short: you cannot move against the direction of this kind of road; if you move in a direction perpendicular to it, you spend time to turn to its direction; if you move along its direction, then it costs no time and you must move two cells at once.** Straight-type roads, turning-type roads, four-way intersections, and forward-type roads cost $a,b,c,d$ units of time, respectively. Due to the strange structure of the countryside, there may be **more than one** entrance and exit. Find the **shortest time** from any entrance to any exit. The directions when entering and leaving are not restricted. --- **Brief statement** Given an $n\times m$ map, find the shortest time from `S` to `E`. Note that there may be multiple start points and multiple end points.

The first line contains six positive integers $n,m,a,b,c,d$ separated by spaces. Then follow an $n$-row, $m$-column character matrix, which contains the above $12$ kinds of characters: ``#``、``|``、``-``、 ``/``、``\``、``.``、````、``^``、`v`、``S``、``E``.

Output the minimum time needed to reach the destination from a start point. If the destination cannot be reached, output `-1`.

#### Sample Explanation Sample #1: Starting from $(1,1)$ and ending at $(3,3)$, the path is $(1,1)\rightarrow(1,2)\rightarrow(1,3)\rightarrow(2,3)\rightarrow(3,3)$. It passes through $3$ four-way intersections, each with cost $4$, so the total cost is $4\times3=12$. Sample #2: Starting from $(1,1)$ and ending at $(1,3)$, the path is $(1,1)\rightarrow(2,1)\rightarrow(2,2)\rightarrow(2,3)\rightarrow(1,3)$. It passes through $2$ turning-type roads and $1$ straight-type road, so the total cost is $2\times2+1\times1=5$. Sample #3: Choose `S` at $(1,1)$ and `E` at $(1,2)$. The entrance and exit are adjacent, so the cost is $0$. Sample #4: Using the forward-type road `>` you can jump one cell directly to `E`. Jumping one cell costs no time. Sample #5: A forward-type road can also be used for turning; in this case its behavior is the same as `/`, and turning also requires time. Sample #6: Here `#` cannot be passed, so there is no path from `S` to `E`. #### Constraints | Subtask ID | Score | $n,m\le$ | Special Property | | :-: | :-: | :-: | :-: | | $1$ | $10$ | $10$ | $\times$ | | $2$ | $15$ | $\times$ | $a=b=c=d=1$ | | $3$ | $20$ | $100$ | $\times$ | | $4$ | $25$ | $\times$ | The number of characters `S` and `E` $=1$ | | $5$ | $30$ | $\times$ | $\times$ | **Please pay attention to the impact of constant factors on program efficiency in this problem.** For $100\%$ of the testdata: $1\le n,m\le2000$, $0\le a,b,c,d\le100$. Translated by ChatGPT 5