Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 1207
The Knight, the Princess, and the Dragons

Time Limit: 2 Seconds      Memory Limit: 65536 KB

A one-story building consists of a rectangular array of rooms. The building will be the scene of a drama whose players are a knight in shining armor, a beautiful princess, and varying numbers of dragons in some of the building's rooms. Such a building (and its current state) will be represented in the format shown in Figure 1.

######
#...K#
#5##0#
#...P#
######

Figure 1. Building floor plan

Each symbol in Figure 1 represents a room. The walls of the building are not shown ; they run in north-south or east-west direction. Specifically, the symbols have the following meaning:

K Initial location of the knight
. <period> A room which will always be free of dragons
0..9 A room which may contain some dragons; the integer represents the current number of dragons
# A permanently obstructed room which the knight may never enter
P Location of the princess, goal of the knight's journey

The east/west rows and north/south columns of rooms are numbered starting with row 0 and column 0 in the building's northwest corner.

Thus the room containing 'K' in the above configuration is designated by (1, 4), meaning row 1 and column 4.

The maximum number of east-west rows of rooms, as well as the maximum number of north-south columns of room in the building's floor plan will not exceed 12.

The rooms along the building's outside walls are #'s.

In those rooms which may contain dragons, the number of dragons in the room changes according to the following rules:

At midnight of each day the weakest dragon is eaten by the other dragon(s), if any.

When there is only one dragon left, it will die of loneliness after 24 hours.

24 hours after the last dragon died, however, the evil spirits will place nine new dragons into the room.

The initial configuration of the building is understood to exist shortly before noon of day 1.

At noon of each day (including day 1), the knight may

either move to an adjacent room (in a north-south or east-west direction)

or stay idle in the current room, if that room is not dragon-prone.

The knight may enter a dragon-prone room (at noon of some day) only if it contains exactly one dragon. The knight is powerful enough to hold one dragon at bay until midnight (when the dragon is going to die of loneliness), but the knight would not have a chance against two or more dragons. Also, if a dragon-prone room is empty at noon, the knight should know not to enter, because as soon as the clock strikes midnight, the room will contain nine dragons.

The knight will not enter the same room twice in a path.

An example of an input is shown in Figure 2.

The input will contain data for one or more knight-princess-dragons problems. (The input shown on the preceding page contains data for six problems.) Each such problem will be represented by

the floor plan/initial configuration as previously discussed

a proposed action sequence for the knight.

Each action sequence will be represented in the input by one line containing at most 80 characters.

The following characters can appear in an action sequence:

. <period> idle
^ <caret> move north
v <lower case V> move south
< <less than> move west
> <greater than> move east

The input will not contain any blank lines, nor any leading or trailing blank spaces.

For each knight-princess-dragons problem in the input, your program will

trace the knight's actions until one of three possible events:

the knight reaches the princess; any further actions in the action sequence will be ignored;

the knight attempts an impossible move or makes a move which will cost his life; again, any further actions in the action sequence will be ignored;

the knight has performed all actions of the action sequence without reaching the princess; ("actions performed, princess not found")

write (to the output)

one blank line

a one-line report summarizing the outcome of the given action sequence.

The contents and format of the one-line report are shown in the sample output below.

######
#...K#
#5##0#
#...P#
######
.<<<vv>>>
######
#...K#
#5##0#
#...P#
######
<<<.vv>>>>
######
#...K#
#5#90#
#...P#
######
.<<<vv>>^^
######
#...K#
#5##0#
#...P#
######
.<<<vv>>^^
######
#...K#
#4##0#
#...P#
######
.<<<vv>>>

Figure 2. Sample input

If the input has the contents shown in Figure 2, then output will be as follows:

Problem 1 by team x

Day  9: entered room          ( 3,  4); princess found

Day  9: entered room          ( 3,  4); princess found

Day 10: attempt to enter room ( 1,  3); previously entered on day  2

Day  9: attempt to enter room ( 2,  3); permanently blocked

Day  5: entered room          ( 2,  1); will be killed by dragons
End of problem 1 by team x

Explanation of the output:

Each report reflects the state of affairs shortly after 12 noon of the day shown.

First report:

On Day 1, the knight stays idle. After three successive left moves, he reaches room (1,1) on Day 4. On Day 5, room (2,1) contains only one dragon, so the knight enters that room safely (by a move down) and the remaining moves get him to the princess on Day 9.

Second report:

After three successive left moves, he reaches room (1,1) on Day 3. On Day 4 (when there are two dragons in room (2,1)) he remains idle, and proceeds to his goal as in the previous action sequence.

The last action (a move to the right) in the action sequence was never executed; it will be ignored.

Third report:

The knight gets past two dragon-occupied rooms at the right time, before attempting to cycle back to a previously occupied room.

Fifth report:

Room (2,1) now contains 4 dragons on Day 1 and no dragon on Day 5, when the knight enters it. At midnight, the room is filled with nine dragons that will immediately kill the knight.

Observe every detail of the output, such as the exact wording and punctuation of statements, upper/lower case variations, blank lines and blank spaces

A few lines of the above output will be reproduced here with formatting templates:

         1         2         3         4         5         6         7
12345678901234567890123456789012345678901234567890123456789012345678901234567
Day 10: attempt to enter room ( 1,  3); previously entered on day  2

Day  9: attempt to enter room ( 2,  3); permanently blocked

Day  5: entered room          ( 2,  1); will be killed by dragons

The day number is right justified in a field of width 3 in columns 4-6. It is also right justified in a field of width 3 in columns 66 - 68 when reporting the day of a previous entry.

The row number of a particular room is right justified in a field of width 2 in columns 32 - 33.

The column number of a particular room is right justified in a field of width 3 in columns 35 - 37.


Submit    Status