首页 > 代码库 > UVA 784 Maze Exploration
UVA 784 Maze Exploration
题目如下:
Maze Exploration
Maze Exploration |
A maze of rectangular rooms is represented on a twodimensional grid as illustrated in figure 1a. Each point of thegrid is represented by a character. The points of room walls aremarked by the same character which can be any printable characterdifferent than `*‘, `_‘ and space. In figure 1 this character is`X‘. All the other points of the grid are markedby spaces.
XXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXX X X X X X X X###X###X###X X X X X X X X###########X X X X X X X X X X###X###X###X X X XXXXXX XXX XXXXXXXXXX XXXXXX#XXX#XXXXXXXXXX X X X X X X X X###X###X###X###X X X * X X X###############X X X X X X X X X###X###X###X###X XXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXX
Figure 1. Mazes of rectangular rooms
All rooms of the maze are equal sized with all walls 3points wide and 1 point thick as illustrated in figure 2. Inaddition, a wall is shared on its full length by the separatedrooms. The rooms can communicate through doors, which arepositioned in the middle of walls. There are no outdoor doors.
door | XX XX X . X measured from within the room door - ...-- walls are 3 points wide X . X__ XXXXX | |___ walls are one point thick
Your problem is to paint all rooms of a maze which can bevisited starting from a given room, called the `start room‘ whichis marked by a star (`*‘) positioned in the middle of theroom. A room can be visited from another room if there is a dooron the wall which separates the rooms. By convention, a room ispainted if its entire surface, including the doors, is markedby the character `#‘ as shown in figure 1b.
Input
The program input is a text file structured as follows:- 1.
- The first line contains a positive integer which shows thenumber of mazes to be painted.
- 2.
- The rest of the file contains the mazes.
The lines of the input file can be of different length. Thetext which represents a maze is terminated by a separation linefull of underscores (`_‘). There are at most 30 lines andat most 80 characters in a line for each maze
The program reads the mazes from the input file, paints themand writes the painted mazes on the standard output.
Output
The output text of a painted maze has the same format as thatwhich has been read for that maze, including the separationlines. The example below illustrates a simple input whichcontains a single maze and the corresponding output.Sample Input
2 XXXXXXXXX X X X X * X X X X XXXXXXXXX X X X X X X XXXXX _____ XXXXX X X X * X X X XXXXX _____
Sample Output
XXXXXXXXX X###X###X X#######X X###X###X XXXXXXXXX X X X X X X XXXXX _____ XXXXX X###X X###X X###X XXXXX _____DFS题,我用两种思路都写了。一种是利用题目的特点直接模拟,一种是DFS,两种思路的代码都给出来。中间RTE了无数次TAT,原因就是把x和y搞反了,一直没发现。找出起始房间然后直接DFS即可,题目挺简单的。
AC的代码如下:
直接模拟版
DFS版