프로그램 명: coci_kruska
제한시간: 1 초
Aladdin has become bored of life at the palace. He has a steady job, his wife Jasmine, kids are on the
way and life is becoming monotonous. Prompted by all this, he has decided to have one more
adventure before settling down.
He has decided to find the Golden Pear, an extremely valuable legendary artifact that no one has been
able to find.
The desert Aladdin is searching is can be modeled as an N×N grid of cells. Rows and columns are
numbered 1 through N top to bottom and left to right. Some of the cells in the desert contain wizards
that help Aladdin's quest in an unusual way.
Aladdin starts his quest in the top left corner of the desert on a Monday facing right. His movement
involves repeating these steps:
- If the current cell contains a wizard that is awake, then Aladdin turns 90 degrees left or right,
depending on what the wizard says.
- If moving forward would take Aladdin out of desert, he turns 180 degrees.
- Aladdin moves forward one cell and it takes him exactly one day.
For each wizard we know his location and his activity schedule for each day of the week. The schedule
is a string of exactly seven letters 'L', 'R' or 'S', each character telling us what the wizard does on one day
of the week (starting with Monday). The letter 'L' means that Aladdin will be told to turn left, 'R' that
Aladdin will be told to turn right, while 'S' means the wizard sleeps that day.
An old prophecy says that after K changes in direction (in steps 1 and/or 2) Aladdin will find the Pear.
Write a program that calculates how many days the search will last, according to the ancient prophecy.
입력
-
The first line contains two integers N and K (2 ≤ N ≤ 200, 1 ≤ K ≤ 1 000 000 000), the size of the
desert and the number of direction changes in the prophecy.
-
The second line contains an integer M (0 ≤ M ≤ 10000), the number of wizards.
-
Each of the following M lines contains two integers R and C (1 ≤ R, C ≤ N), and a string of seven
letters 'L', 'R' or 'S'. The numbers represent the row and column where the wizard is located, while the
string is his schedule.
No two wizards will share the same cell, nor will there be a wizard in cell (1, 1).
출력
Output the length of the search in days.
입출력 예
input
3 1
0
output
2
input
5 2
2
1 3 RRSRRRR
1 5 RRRRLRR
output
4
output
5 5
3
1 3 SSRSSSS
3 3 SSSLSSS
4 3 SSRSSLS
output
10
sample
In the first example, Aladdin moves twice, reaching the edge of the desert. He then turns 180 degrees
and finds the Pear.
In the second example, Aladdin reaches the first wizard on the third day, but the wizard is sleeping so
Aladdin continues in the same direction. After two more days he reaches the other wizard who tells
him to turn left. Aladdin does so, reaches the edge of the desert, turns back and finds the pair.
출처: coci 2008/2009 contest5 6/6
[질/답]
[제출 현황]
[푼 후(0)]