TopCoder

Thumb ya2
赤ずきんチャチャ
もっと心の中を二人見せ合えたなら 答えはつかめるよ

User's AC Ratio

100.0% (7/7)

Submission's AC Ratio

31.7% (13/41)

Tags

Description

某天你在家裡的地上放了一個大冰塊,希望它趕快融化掉(這樣才能趕快吸走家裡空氣中的熱),此時台灣發生了大地震,而你家裡的所有物品早已固定好了,因此你希望可以讓冰塊在家裡滑行最長的距離。
地震所有可能往上下左右這四種方向搖,而你只能讓冰塊停住或是讓其順著重力往搖的方向滑過去(速度每秒1格磁磚),然後冰塊撞到障礙物會停住。

Input Format

輸入的第一行包含的4個數N,M,x,y,N和M表示你家的大小,x和y是你冰塊的初始位置。
接下來的N行是你家的平面圖,*代表障礙物,.代表沒有東西。
接著是一個正整數k,代表地震搖了k下。
最後有k行,每行有2個整數Qi,Pi,代表每下搖的方向跟搖的時間。
而1,2,3,4分別代表上下左右。

2<=N,M<=300
0<x<=N
0<y<=M
0<=k<=300
1<=Pi<=Max(N,M)

Output Format

輸出冰塊可滑行的最大長度。

Sample Input

4 5 4 1
..**.
.....
...*.
.....
3
4 3
1 2
2 2

Sample Output

6

Hints

冰塊好吃嗎?

Problem Source

Subtasks

No. Testdata Range Score
1 0~9 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 500 65536 262144 1
1 500 65536 262144 1
2 500 65536 262144 1
3 500 65536 262144 1
4 500 65536 262144 1
5 500 65536 262144 1
6 500 65536 262144 1
7 500 65536 262144 1
8 500 65536 262144 1
9 500 65536 262144 1