National Olympiad in Informatics, China, 2005

Day 1, Problem 1 - The Magnificent Waltz

Have you ever waltzed before? When the music starts, when you're moving your feet along with the melody, isn't it just like taking a leisurely stroll through Wonderland?

As we all know, the most important thing for waltzing is to have good music. However, very few people know that the greatest pianist in the world spends his entire life wandering the oceans. His name is Danny Boodman T.D. Lemon 1900, although his friends simply call him 1900.

1900 was born in the first year of the 20th century on the SS Virginian, a cruise ship sailing between Europe and America. Unfortunately, he was abandoned right after he was born, becoming an orphan. Growing up on the Virginian, 1900 has never traveled outside of his shaky world. Maybe to compensate for his fate, God has sent the cute little angel Emily to take care of him.

Perhaps due to the angel's guidance, 1900 now has an unbelievable talent for the piano. Never having been taught and never having seen any musical scores, he is able to use his own feelings to produce the most touching melodies. When 1900's music was receiving praise from everybody on the cruise ship, he was only 8 years old. By then, he had already ridden the ship back and forth between Europe and America roughly 50 times.

Despite being a piano prodigy, 1900 is still a child. He possesses the same curiosity and mischievousness as any other boy, only with an additional layer of romantic flare.

One stormy night, the ocean winds conjured up thick, thick waves, smacking them against the SS Virginian. The cruise ship shook violently with the giant waves. Tony Michaels, the new Saxophonist on board became seasick. 1900 signaled Tony over to sit with him atop the ballroom piano. After releasing the brakes that secured the piano, the instrument began to slide around based upon the tilt of the ship. More specifically: our protagonist 1900, the piano, and the cruise ship, started to waltz alongside 1900's melody. Dancing along the "Ba-Cha-Cha" rhythm, Tony's seasickness has miraculously vanished. Afterwards, Tony added the following to his diary:

The sea shakes us about
Making us rock back and forth
Dashing around lamps and furniture
I realize that we are dancing with the ocean
Truly a perfect and crazy dancer

Isn't it so pleasant to be happily waltzing on the golden floorboards at night? Maybe we forgot someone… and that person is Emily! She certainly hasn't been idle during all this. Emily must wait for the right time to cast her magic and help 1900, preventing the piano from colliding with the furniture.

It won't hurt to describe the ballroom as a grid of N rows by M columns, where certain cells of the grid contain furniture and other cells are empty. The piano may slide along empty areas on the ground, but may not hit any furniture or slide out of the ballroom, otherwise the piano or furniture may be damaged, resulting in trouble with the Captain.

At every moment, the piano will follow the direction of the ship's tilt and slide one unit to the adjacent cell in the north, south, east, or west directions. Additionally, Emily can choose to cast her magic or not to cast her magic. If no magic is cast, the piano will slide; if magic is cast, the piano will remain in its original spot.

Since Emily is an angel, she will know the tilt status of the ship during every period of time. She would like the path of the piano in the ballroom to be as long as possible. This will make 1900 very happy, and also help out Tony with his seasickness. However Emily is still too young and doesn't know how to count, so she wishes for you to help her.

Input Format

The first line of input contains 5 integers N, M, x, y, and K. N and M describe the size of the ballroom while x and y describe the initial position of the piano. We shall describe the status of the ship using intervals of time, starting at time 1. For example, the ship tilts "east during [1, 3], north during [4, 5]", and so forth. K will indicate the number of such time intervals.

In the following N lines, each line contains M characters, describing the furniture arrangement in the ballroom. If on line i the j-th character is '.', then the location indicated is empty. If the character is 'x', then the location indicated contains furniture.

The remaining K lines describe the K time intervals in the format: s_i t_i d_i (1 ≤ i ≤ K). This indicates that within the time interval [s_i, t_i], the ship tilts in direction d_i. d_i is one of the numbers 1, 2, 3, or 4, respectively representing north, south, west, and east (up, down, left, and right in the grid). The input guarantees that ranges will be consecutive, that is:

s₁ = 1
t_i = s_i−1 + 1 (1 < i ≤ K)
t_K = T

Output Format

The output should consist of 1 line, containing a single integer - the maximum distance that the piano can slide (in grid cells).

Sample Input

4 5 4 1 3
..xx.
.....
...x.
.....
1 3 4
4 5 1
6 7 3

Sample Output

6

Explanation

The path of the sliding piano is as follows:

The angel casts her magic when the piano reaches the "X" spot. Thus, the total distance that the piano slides is 6.

Constraints

In test data worth 50% of points, 1 ≤ N, M ≤ 200, T ≤ 200;
In test data worth 100% of points, 1 ≤ N, M ≤ 200, K ≤ 200, T ≤ 40000.

All Submissions
Best Solutions

Point Value: 20 (partial)
Time Limit: 1.00s
Memory Limit: 256M
Added: Jun 02, 2014

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)