Programming contests

ECN selejtező programozó csapatverseny, 2015. április 19.

April 19, 2015 10:10 AM – April 19, 2015 3:10 PM

Maze Traversal

A common problem in artificial intelligence is negotiation of a maze. A maze has corridors and walls. You have a robot, which can proceed along corridors but cannot go through walls. Your task is to find the final position and orientation of the robot, given its initial position and orientation and a set of movements.

Input Specification

The input begins with a single positive integer in a line by itself, indicating the number of test cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

The first line of each test case contains the dimensions of a maze as two integer values. Of the two numbers, the first is the number of rows, and the second is the number of columns. Neither the number of rows nor the number of columns will exceed 60.

Following these numbers will be a line for each row of the maze. In each line, there will be a character for each column, with the row terminated by the end of line. Blank spaces are corridors, asterisks are walls. There needn’t be any exits from the maze.

Following the maze, the initial row and column of the robot will be specified as two integers in one line. Initially, the robot will be facing north (toward the first row).

The remaining input will consist of commands to the robot, with any amount of interspersed whitespace. The valid commands are:

  • R: rotate the robot 90 degrees clockwise (to the right)
  • L: rotate the robot 90 degrees counterclockwise (to the left)
  • F: move the robot forward unless a wall prevents this, in which case, do nothing
  • Q: quit the program, printing out the current robot row, column, and orientation

Output Specification

For each test case, the output must follow the description below. The outputs of two consecutive cases must be separated by a blank line.

The final row and column must be two integers separated by a space. The orientation must be one of N, W, S, or E (representing north, west, south, and east, respectively) and separated from the column by a space.

Sample Input

  1. 1
  2. 7 8
  3. ********
  4. * * * **
  5. * *    *
  6. * * ** *
  7. * * *  *
  8. *   * **
  9. ********
  10. 2 4
  11. RRFLFF FFR
  12. FF
  13. RFFQ
download as text file

Output for Sample Input

  1. 5 6 W
download as text file
University of Debrecen; Faculty of Informatics; v. 03/01/2019