uva 784 Maze Exploration（DFS遍历图）

                         uva 784 Maze Exploration

maze(迷宫) of rectangular(矩形的) rooms is represented on a two dimensional(空间的) grid as illustrated(阐明) in figure 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 figure 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

maze (迷宫)                    b) Painted maze

Figure 1. Mazes of rectangular(矩形的)

illustrated(阐明)

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

*') 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 figure 1b.

Input 

The program input(投入) is a text file structured(有结构的)

positive (积极的) integer (整数) 2. The rest of the file contains the mazes.

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(迷宫)

input(投入) file, paints them and writes the painted mazes on the standard output(输出).

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 example below illustrates(阐明)

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遍历的同时直接修改map.

#include<stdio.h>
#include<string.h>
char map[35][85], cnt = 0;
void DFS(int a, int b) {
	map[a][b] = '#';
	for (int i = -1; i <= 1; i++) {
		for (int j = -1; j <= 1; j++) {
			if (i == 0 && j == 0) {
				continue;
			}
			if (a + i < 0 || a + i > cnt) {
				continue;
			}	
			if (b + j < 0 || b + j > strlen(map[a + i])) {
				continue;
			}
			if (map[a + i][b + j] == '#' || map[a + i][b + j] == 'X') {
				continue;
			}
			DFS(a + i, b + j);
		}
	}
}	
int main() {
	int n;
	scanf("%d\n", &n);
	while (n--) {
		memset(map, 0, sizeof(map));
		cnt = 0;
		while (gets(map[cnt]) != NULL) {  
			if (strcmp(map[cnt], "_____") == 0) { 
				break;  
			}
			cnt++;  
		}
		for (int i = 0; i <= cnt; i++) {
			for (int j = 0; j < strlen(map[i]); j++) {
				if (map[i][j] == '*') {
					DFS(i, j);
				}
			}
		}
		for (int i = 0; i <= cnt; i++) {
			puts(map[i]);
		}
	}
	return 0;
}