1813 . 地震冰塊
TopCoder
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 1
4 5 4 1
..**.
.....
...*.
.....
3
4 3
1 2
2 2
..**.
.....
...*.
.....
3
4 3
1 2
2 2
Sample Output 1
6
Hints
冰塊好吃嗎?
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~9 | 100 |