In the event of technical difficulties with Szkopuł, please contact us via email at firstname.lastname@example.org.
If you are familiar with IRC chat, the support team is also reachable on PIRC network (
#szkopul channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
Byteman has received an extraordinary keyboard as a gift. The keyboard is a rectangle consisting of rows and columns with keys placed on it. Moreover, all keys except the one in the top left corner are covered with domino tiles of size , so there are domino tiles in total. At any time, Byteman can move onto the free key one of the domino tiles adjacent to it by the shorter side. He can also press keys, but only if they are not covered.
Byteman would like to test (i.e., press) all the keys corresponding to vowels, that is, the letters a, e, i, o, u or y. What is the minimum number of tile moves necessary to do that?
The first line of the input contains two integers and () that describe the dimensions of the keyboard. The next lines contain lowercase letters of the English alphabet each, describing the rows of the keyboard. Each of the next lines contains characters describing placement of the domino tiles: . (ASCII code 46) denotes an uncovered key, - (ASCII code 45) denotes a key covered by a domino tile placed horizontally and | (ASCII code 124) - a key covered by a tile placed vertically.
If it is not possible for Byteman to press all the keys corresponding to vowels, your program should output just the single word "NIE" (i.e. yes in Polish). Otherwise output the minimum number of tile moves that Byteman must make in order to press all the requested keys.
For the input data:
3 3 ytr hgf dsa .-- ||| |||
the correct result is:
Task author: Jakub Pachocki.