NonOptimalMazeSolver | Topcoder Archive

Problem Statement

A maze is defined as a String[] representing a grid of cells. The j-th character of the i-th element of maze is a character that represents cell (i,j). Cell is 'X' if the cell is a wall and thus cannot be visited. Empty cells are '.', 'S' or E'. The starting cell is an empty cell marked with 'S' and the goal cell is marked with 'E'.

If the current player position is cell (i,j), There are 4 allowed moves:

U : (Up) Moves to (i-1, j).
D : (Down) Moves to (i+1, j).
R : (Right) Moves to (i, j+1).
L : (Left) Moves to (i, j-1).

If the destination cell contains a wall, the move is invalid and should not be used.

You have plenty of mazes to solve, you don't want to get bored solving them all. Instead you will make a program to solve each of the mazes. However, if the returned sequence of moves is too short, it would be too obvious you are using a computer to solve them. This is the reason your program is not meant to find the shortest path between the start and the goal cell, but a path that is larger than that.

Formally, assume that the minimum number of steps/moves needed to reach the goal cell was T. Tthen the sequence of steps your program returns must contain at least 2*T steos. The path is defined as a String of characters: U,D,L and R each representing the moves to do, the 0-th character represents the first move. The returned path should never visit a wall cell. The returned path is not allowed to visit the goal cell more than exactly once and the goal must be the last cell visited by the path. The other empty cells, including the starting cell may be visited multiple times.

If there exists a sequence of moves that solves the maze with the required conditions, return any valid sequence. If there is no possible path between the start and goal cell, return "Invalid". If it is impossible to make a path that is twice as long as the optimal path, return "Cannot".

Definition

Class:: NonOptimalMazeSolver
Method:: getAPath
Parameters:: String[]
Returns:: String
Method signature:: String getAPath(String[] maze)
(be sure your method is public)

Notes

Due to technical constraints the returned path shouldn't contain more than 1000 characters. It can be shown that with the constraints given below, if valid paths exist for a given case, at least one of them will have a length smaller than 1001.

Constraints

n and m will each be between 3 and 20, inclusive.
maze will contain n elements.
Each element of maze will contain exactly m characters.
Each character in maze will be '.' , 'X', 'S' or 'E'.
maze will contain exactly one 'S' character and one 'E' character.
maze[0] and maze[n-1] will contain only walls.
The left-most and right-most columns of maze will contain only walls.

Examples

```
{"XXXXXXXX",
 "X......X",
 "X..X...X",
 "X..X...X",
 "X.SXE..X",
 "X......X",
 "XXXXXXXX"}
```
```
Returns: "UUURRDDD"
```
The optimal path is: "DRRU", of length 4. So the returned path should have a length of at least 8. The path "UUURRDDD" finishes at the exit cell and has length 8, so it is a good result to use. Another valid result is: "UULDDDRRRU", even though it does not have exactly 8 steps.

{
 "XXXXXX",
 "X.X.EX",
 "X.XX.X",
 "XS.X.X",
 "XXXXXX"
}

Returns: "Invalid"

This maze is unsolvable.

```
{"XXXX",
 "XESX",
 "XXXX"}
```
```
Returns: "Cannot"
```
The only path possible is "R", a longer path is impossible because the goal cell must only be visited once.

{"XXXXXXXXX",
 "X...S...X",
 "X.XXXXX.X",
 "X.X...X.X",
 "XEX.X.X.X",
 "X...X...X",
 "XXXXXXXXX"}

Returns: "RRRDDDDLLUULLDDLLU"

{"XXXX",
 "X.EX",
 "XSXX",
 "XXXX"}

Returns: "UDUR"

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.