2014
11-29

Go , SuSu

When SuSu and his friends visited GanQuan village , something dangerous happened on them . They were trapped in a mysterious cave , what was worse ,there was a terrible monster lived in the cave , so they had to escape from the cave as quickly as possible .

But little monsters were also in the cave, as a result ,when SuSu was seen by the little monsters ,they would notice their boss to catch SuSu back.
Little monsters’ visual field is showed in figure A. The grid colored red represents where the monster stands, the arrow represents which direction the monster walk to ,and the grids colored blue and red represents where the very monster can see at this moment. The monsters often walks in a straight line, and when they faces a wall or the boundary of the maze in front of him, they will cost 1 seconds to turn back, and then walk back along the straight line, until reach a wall again.
If SuSu was seen by the monsters ,it’s impossible for them to escape from the cave . SuSu needs your help , please tell him the minimum time he needs to walk from the start point to the exit of the cave , be careful not to be seen by the monsters. Every seconds SuSu can move upward downward leftward and rightward , and can also make no movement.

Figure A

The first line of input gives the number of cases, T (at most 90).
the first line of each case has four numbers n,m. (2<=n,m<=50)
then n lines with m characters describe the maze
‘A’ represents the init position of SuSu.
‘B’ represents the exit position of the cave.
‘.’ represents the grids can be walked on.
‘*’ represents the wall which can not be stepped on.
Then follows a number k (at most 50).
Next k lines with three integers x , y , d (1 <= x <= n,1 <= y <= m,1 <= d <= 4).represents a monster walking to d direction is in (x,y) positon (the top-left grid is (1,1) ) at 0 seconds .
The monster walks up when d == 1. walk down when d == 2.walk left when d == 3.walk right when d == 4.

The first line of input gives the number of cases, T (at most 90).
the first line of each case has four numbers n,m. (2<=n,m<=50)
then n lines with m characters describe the maze
‘A’ represents the init position of SuSu.
‘B’ represents the exit position of the cave.
‘.’ represents the grids can be walked on.
‘*’ represents the wall which can not be stepped on.
Then follows a number k (at most 50).
Next k lines with three integers x , y , d (1 <= x <= n,1 <= y <= m,1 <= d <= 4).represents a monster walking to d direction is in (x,y) positon (the top-left grid is (1,1) ) at 0 seconds .
The monster walks up when d == 1. walk down when d == 2.walk left when d == 3.walk right when d == 4.

1
3 4
*.*.
.A.B
***.
1
3 4 1

Case 1: 2

1. 给你一组数据吧：29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的，耗时却不短。这种方法确实可以，当然或许还有其他的优化方案，但是优化只能针对某些数据，不太可能在所有情况下都能在可接受的时间内求解出答案。

2. 5.1处，反了；“上一个操作符的优先级比操作符ch的优先级大，或栈是空的就入栈。”如代码所述，应为“上一个操作符的优先级比操作符ch的优先级小，或栈是空的就入栈。”

3. #include <cstdio>

int main() {