14958 - Cat Teleport Maze   

Status  |  Limits Submit

Description

Please implement the following game by completing all methods marked with TODO in the provided header code.
Please submit with C++17.


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

  • 'S': starting position of the cat
  • 'E': exit position
  • '#': wall
  • '_': empty cell
  • '+': food
  • 'a' - 'z': teleport cell

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.

Some pairs of cells are connected by teleportation. Each cell belongs to at most one teleport pair.

The cat cannot move onto a wall cell.

Initially, the entire maze is unknown to the cat.

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

  1. sees and memorizes the adjacent cells and the paired teleport cell if the current cell has one;
  2. moves to either an adjacent cell or the paired teleport cell, if one exists.

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 the specified number of steps. This is guaranteed to be possible for all given test cases.

 

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.

 

Note

Two cells with the same lowercase letter are paired teleport cells.

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

  • Subtask 1 contains no teleport pairs and has the step limit 10000.
  • Subtask 2 contains no food cells and has the step limit 10000.
  • Subtask 3 has the starting position and the exit cell in adjacent cells and the step limit 10000.
  • Subtask 4 has the step limit 10000.
  • Subtask 5 has the step limit 1500.

 

Output

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

If the cat eats all food and reaches the exit within the specified number of steps, the program outputs SUCCESS.

Otherwise, the program outputs FAIL.

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

 

Sample Input  Download

Sample Output  Download

Partial Judge Code

14958.cpp

Partial Judge Header

14958.h

Tags




Discuss