# Programming contests

## DEIK Regionális Programozó Csapatverseny, nyílt kategória, 2019. december 8.

December 8, 2019 10:15 AM – December 8, 2019 3:15 PM

# Chaotic Maze

Guest 2019 is lost and can't find the park exit. – came the message in Viktor's favorite computer game, RollerCoaster Tycoon. Generations enjoyed the 20-year-old theme park simulator game, which was designed by Chris Sawyer in 1999. Despite of this, it still causes a nightmare when visitors get lost in the complex path system of the park.

A while ago, Viktor found the installer of his favorite game. As a smart programmer, he made up his mind to decompile the game code to source code in C language and started to rewrite the code of Hedge Maze so that it now works in an absurd way. When entering the park, the visitors find themselves at a random point of the maze and have to find the exit field for getting out. With each move, a visitor can take exactly one step onto a field having exactly one common side with the visitor's current field. They can, however, teleport at the edges of the maze: they can move from the rightmost field of a row to the leftmost field of the same row, from the leftmost field of a row to the rightmost field of the same row, from the top field of a column to the bottom field of the same column, and from the bottom field of a column to the top field of the same column. Viktor did not change one thing: visitors cannot move to a field containing a wall.

## Input Specification

Mazes are always rectangular. The first line of the input contains two integers separated by a single space: the first is the number of rows N, and the second is the number of columns M (2 ≤ NM ≤ 100). This is followed by N lines, each containing M characters. An empty field is denoted by `'.'` (the dot character), the wall is denoted by `'x'` (the lowercase letter x), the start field is denoted by `'S'`, and the exit field is denoted by `'E'`.

## Output Specification

The program should output one line. If the visitor can reach the exit, and they can do it in N steps in an optimal way, then output “`Guest 2019 needs N steps to find the maze exit.`”. If the exit is unreachable, the line „`Guest 2019 cannot find the maze exit.`” should be printed.

## Sample Input 1

1. `10 10`
2. `xxxxx.....`
3. `..S.x.....`
4. `....x.....`
5. `....x.....`
6. `....x.....`
7. `....x.....`
8. `....x.....`
9. `....xxxxxx`
10. `.....x.E..`
11. `.....x....`

## Output for Sample Input 1

1. `Guest 2019 needs 8 steps to find the maze exit.`

## Sample Input 2

1. `10 10`
2. `xxxxxxxxxx `
3. `..S.x.....`
4. `....xxxxxx`
5. `....x.....`
6. `xxxxx.....`
7. `....x.....`
8. `....xxxxxx`
9. `....x.....`
10. `xxxxxx....`
11. `..E..x....`

## Output for Sample Input 2

1. `Guest 2019 needs 16 steps to find the maze exit.`