Description

 

A cat is trapped in a 20×20 maze. Each cell is one of the following types:

• 'S': starting position
• 'E': exit position
• '#': wall
• '_': empty cell
• '+': food

The cat starts at 'S'. Initially, the whole maze is unknown to the cat.

The game proceeds in steps. In each step, the cat does the following:

1. see and memorize cells adjacent to its current position, and then
2. move to an adjacent cell based on its memory.

Two cells are adjacent if they share a side, that is, if one is directly above, below, to the left of, or to the right of the other.

When the cat moves onto a cell with food, the food is eaten and the cell becomes empty immediately.

Your goal is to make the cat eat all food and then reach the exit cell within 10000 steps.

 

Note

• Moving onto the exit cell before eating all food is allowed and does not cause the game to fail.
• All non-wall cells in the maze are guaranteed to be connected.
• The cat cannot move onto a wall cell.

 

Input

(The input is already handled by the provided C++ code.)

The input contains exactly 20 lines.

Each line contains exactly 20 characters, representing the maze.

The maze contains exactly one S and exactly one E.

The outer boundary of the maze is guaranteed to be #. (See the sample input for an example.)

---

Subtasks:

• Testcase 1 is the sample input.
• Testcase 2 contains no wall cells other than the outer boundary, and contain no food cells.
• Testcases 3 and 4 contain no food cells.
• Testcases 5, 6, and 7 have the starting position and the exit cell in adjacent cells.
• Testcases 8, 9, and 10 are general cases without additional restrictions.

 

Output

(The output is already handled by the provided C++ code.)

Output one line.

If the cat eats all food and reaches the exit within 10000 steps, output: SUCCESS.

Otherwise, output: FAIL.

You will receive an AC only if the program outputs SUCCESS.

 

Sample Input  Download

Sample Output  Download

Partial Judge Code

14951.cpp

Partial Judge Header

14951.h

Discuss