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

Ural Regional School Programming Contest 2019

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. BitMazeCraft

Time limit: 3.0 second
Memory limit: 256 MB
Vlad is a very responsible employee. But instead of working he plays BitMazeCraft. But not the survival mode, he prefers completing user-created maps. As you might guess, it’s very difficult. Especially when Vlad’s co-workers interrupt him constantly.
Today Vlad is trying to complete a map of size A × B × H, where H is the map’s height. He needs to move the character from one spot to another without leaving the map’s boundaries. The map consists of 1× 1× 1 cubes, each cube has coordinates (x, y, z) and is either occupied by a wall or empty (1 ≤ xA, 1 ≤ yB, 1 ≤ zH). Vlad is a bit anxious about his boss showing up, so he wants to complete the map as soon as possible. To “complete the map” means to move the character from start to finish.
Let’s say that a cell is located above the floor if either it’s z coordinate is equal to 1 or the cube below it is occupied. The controls in BitMazeCraft are simple: the character has size 1× 1× 1 and it must be located in an empty cell above the floor at all times. The character has four types of movement, every one takes up the same amount of time.
  • moving horizontally into a neighboring cell ((x, y, z){(x, y ± 1, z), (x± 1, y, z)}) if the target cell is empty and above the floor (such movement is called walk)
  • moving horizontally over the neighboring cell ((x, y, z){(x, y ± 2, z), (x ± 2, y, z)}) if both cells in the direction of movement are empty; the cell character passes over ({(x, y ± 1, z−1), (x± 1, y, z−1)}) is empty (otherwise the character would tumble); and the target cell is above the floor (such movement is called jump)
  • descent by one layer while moving into a neighboring cell laterally ((x, y, z){(x, y ± 1, z−1), (x± 1, y, z−1)}) if the target cell is empty and above the floor; and the cell above the target cell is also empty (such movement is called drop)
  • ascent by one layer while moving into a neighboring cell laterally ((x, y, z){(x, y ± 1, z+1), (x ± 1, y, z+1)}) if the cell above the starting cell is within the bounaries of the map and empty; and the target cell is empty and above the floor (such movement is called climb).
In fact, Vlad isn’t even sure if the map can be completed at all. So he asked you to check if the map can be completed, and if that’s true, what’s the fastest way to get from start to finish.

Input

The first line contains three space-separated integer numbers A, B, H — length, width and height of the map (1 ≤ A, B, H ≤ 50). Then, H · A lines of length B grouped into H blocks with A lines each are given.
Each block describles the slice of the map with a fixed z coordinate. They are given from bottom to top, in the ascending order of z. Each line describes a slice of a block with a fixed x coordinate, lines within a block are given in ascending order of x. Characters in a line describe cells and are given in ascending order of y. Character “#” (code 35) denotes an occupied cell, character “.” (code 46) denotes an empty cell.
The last two lines contain three space-separated integers each — starting point of the characted xfrom, yfrom, zfrom and the destination point xto, yto, zto respectively (1 ≤ xfrom, xtoA, 1 ≤ yfrom, ytoB, 1 ≤ zfrom, ztoH).
It is guaranteed that both the starting cell and the destination cell are empty and are above the floor.

Output

If it’s impossible to complete the map, output “NO” (without quotes) in a single line.
Otherwise, output “YES” (without quotes) in the first line. In the second line, output an integer N — the minimal amount of moves to complete the level. In each of next N lines, output the moves in the following format: typei directioni, where typei is the type of movement “walk”, “jump”, “drop” or “climb” (without quotes); directioni — the direction of movement “north”, “east”, “south” or “west” (without quotes): north — moving from (x, y, z) to (xk, y, z'), east — from (x, y, z) to (x, y+k, z'), south — from (x, y, z) to (x+k, y, z') or west — from (x, y, z) to (x, yk, z'); where k is equal to 2 if typei is jump and 1 otherwise; z' equals to z if typei is walk or jump, z − 1 if typei is drop and z + 1 if typei is climb.
If there are many optimal ways to complete the map, you may output any one of them.

Samples

inputoutput
1 2 1
..
1 1 1
1 2 1
YES
1
walk east
3 4 2
.#..
....
.#..
....
....
....
1 1 1
3 4 1
YES
4
climb east
jump south
drop east
walk east
Problem Author: Vadim Barinov
Problem Source: Ural School Programming Contest 2019
To submit the solution for this problem go to the Problem set: 2140. BitMazeCraft