International Competitive Programming Competition

The ICPC maintains a list of past programming problems from world finals in the past - link.

2000 - Dice Maze

The ICPC world finals in the year 2000 focused on the concept of a "dice maze" - a special type of maze in which the directions in which you are allowed to travel depend on the direction in which you are traveling.

The maze consists of a grid of intersections connected by hallways. As are most mazes, a walk-through dice maze, or "arrow maze," is traversed by moving from intersection to intersection until the goal intersection is reached.

As each intersection is approached from a given direction, a sign near the entry to the intersection indicates in which directions the intersection can be exited. These directions are always left, forward or right, or any combination of these.

The ICPC programming challenge was (is?) to write a program to solve any valid walk-through maze. This means finding the shortest possible solution, if a solution is in fact possible.

SAMPLEMAZE
3 1 N 3 3
1 1 WL NR *
1 2 WLF NR ER *
1 3 NL ER *
2 1 SL WR NF *
2 2 SL WF ELF *
2 3 SFR EL *
0

This can be executed by putting it into in.txt, and passing the input to the Java program as follows:

$ MY_PROGRAM < input_file.txt > output_file.txt