ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Romanian Open Contest December 2001

About     Problems     Submit solution     Judge status     Standings
Contest is over

E. Lost in Space

Time limit: 1.0 second
Memory limit: 4 MB
An astronaut of the RSA (Romanian Space Agency) was "forgotten" on the N-th level of a Romanian Space Station. He wants to go down to the 1st level, where the communication devices are located, so he can call a space ship to take him home. Unfortunately, the astronaut doesn't know how long the ship will take until it gets to the space station. That's why he wants to gather as much space food as possible before he sends out the message to the ship.
Every level of the space station contains 16 rooms, arranged in 4 rows and 4 columns (numbered accordingly). Every room contains an amount of space food (a number between 1 and 255).
The astronaut may move freely inside the space station, but he is not allowed to visit the same room twice. Moreover, if he went to a lower level, he is not allowed to move back to a higher level. From every room, he could move either north, south, east or west (on the same level) or down (on the same row and column, but at the level below), if there is a door to the level below in that room. For each level, a map is given which tells which rooms have doors to the level below them.
Whenever he enters a room, the astronaut gets the amount of space food found in that room. The food ratio of the astronaut is defined as the total quantity of food gathered during his trip inside the space station divided by the number of days he spends inside the space station before he sends out the signal to the space ship. It is considered that the astronaut spends the 1st day in the room he begins his trip, on the N-th level, and that he gets the amount of space food found in this room during this day. He is only allowed to move once per day.
You have to find a path from the N-th level to the 1st level, which has the maximum food ratio. Note that the astronaut does not have to call the ship as soon as he gets to a room on the 1st level. He may move around the level first, gather the necessary food and only then call the ship.


The first line of input contains a single number: N (1 ≤ N ≤ 16), the number of levels of the space station. For each level, there will be 8 lines of input containing its description. The first four lines will contain four integers, representing the amount of space food found in the corresponding room on that level (the number found on the j-th position on the i-th line represents the amount of food in the room found on row i and column j on the level). The next four lines will contain four integers, in the range 0..1. 1 means that there is a door from that room to the level below, 0 means that there isn't one. Level 1 will have only 0s on these four lines (there is no level below level 1).
The order of the levels in the input will be from top to bottom (from level N to level 1). The last line of input will contain 2 numbers r and c, representing the row and column of the room the astronaut is initially in, on level N.


On the 1st line, you should output the maximum possible food ratio for the astronaut, with 4 decimal digits. On the 2nd line you should output the length of his path (print 0 if the astronaut never gets out of the room he is initially found in). If the length of his path is L, L > 0, then on the 3rd line of output you should output L characters: 'N', 'E', 'S', 'W' or 'D', each character corresponding to one direction of movement (north, east, south, west and down). If there are more solutions with the same maximum food ratio, then you may output any of them.
Note that, if L is the length of the astronaut's path, then he spends L+1 days before he calls the space ship.
Every test case is guaranteed to have at least 1 solution.


1 20 1 1
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
0 0 0 0
0 0 0 0
0 0 0 0
1 1 1 1
20 1 1 1
1 1 1 1
1 1 1 1
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 1
Problem Author: Mugurel Ionut Andreica
Problem Source: Romanian Open Contest, December 2001
To submit the solution for this problem go to the Problem set: 1171. Lost in Space