首页 > 代码库 > uva 784 - Maze Exploration
uva 784 - Maze Exploration
784 - Maze Exploration
A maze of rectangular rooms is represented on a two dimensional grid as illustrated in gure 1a.
Each point of the grid is represented by a character. The points of room walls are marked by the
same character which can be any printable character different than `
*
‘, `
‘ and space. In gure 1 this
character is `
X
‘. All the other points of the grid are marked by 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
a) Initial maze
b) Painted maze
Figure 1. Mazes of rectangular rooms
All rooms of the maze are equal sized with all walls 3 points wide and 1 point thick as illustrated
in gure 2. In addition, a wall is shared on its full length by the separated rooms. The rooms can
communicate through doors, which are positioned 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
Figure 2. A room with 3 doors
Your problem is to paint all rooms of a maze which can be visited starting from a given room, called
the `start room‘ which is marked by a star (`
*
‘) positioned in the middle of the room. A room can be
visited from another room if there is a door on the wall which separates the rooms. By convention, a
room is painted if its entire surface, including the doors, is marked by the character `
#
‘ as shown in
gure 1b.
Input
The program input is a text le structured as follows:
1.
The rst line contains a positive integer which shows the number of mazes to be painted.
2.
The rest of the le contains the mazes.
The lines of the input le can be of different length. The text which represents a maze is terminated
by a separation line full of underscores (`
‘). There are at most 30 lines and at most 80 characters in a
line for each maze. The program reads the mazes from the standard input.
Output
The output text of a painted maze has the same format as that which has been read for that maze,
including the separation lines. The program writes the painted mazes on the standard output.
SampleInput
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
_____
SampleOutput
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
_____
#include <iostream>#include <stack>#include <cstring>#include <cstdio>#include <string>#include <algorithm>#include <queue>#include <set>#include <map>#include <fstream>#include <stack>#include <list>#include <sstream>#include <cmath>using namespace std;#define ms(arr, val) memset(arr, val, sizeof(arr))#define mc(dest, src) memcpy(dest, src, sizeof(src))#define N 85#define INF 0x3fffffff#define vint vector<int>#define setint set<int>#define mint map<int, int>#define lint list<int>#define sch stack<char>#define qch queue<char>#define sint stack<int>#define qint queue<int>char maze[N][N];int dir[4][2] = {0, -1, -1, 0, 1, 0, 0, 1};void dfs(int i, int j){ maze[i][j] = ‘#‘; int ii, jj; for (int k = 0; k < 4; k++) { ii = i + dir[k][0]; jj = j + dir[k][1]; if (ii >= 0 && jj >= 0 && maze[ii][jj] && maze[ii][jj] == ‘ ‘) { dfs(ii, jj); } }}int main(){ int t; scanf("%d", &t); getchar(); while (t--) { int n = 0, i = 0, j = 0; while (gets(maze[n]), maze[n++][0] != ‘_‘); while (true) { if (maze[i][j]) { if (maze[i][j] == ‘*‘) { dfs(i, j); break; } } else { i++; j = -1; } j++; } i = 0; do { puts(maze[i]); } while (maze[i++][0] != ‘_‘); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。