[UVa]532:Dungeon Master

三維的BFS即可得解。

[C](0.016)

	#include<stdio.h>
	int min( int a, int b )
	{
	return ( a < b ) ? a : b;
	}
	int main()
	{
	int L, R, C;
	while( scanf( "%d%d%d", &L, &R, &C ) != EOF && L != 0 && R != 0 && C != 0 )
	{
	char map[35][35][35] = {0};
	char s[35];
	int i, j, k;
	int BFS[30000][5] = {0}, bfs_num = 0;
	int label[35][35][35] = {0};
	for( i = 1 ; i <= L ; i++ )
	for( j = 1 ; j <= R ; j++ )
	{
	scanf( "%s", s );
	for( k = 1 ; k <= C ; k++ )
	{
	map[i][j][k] = s[k-1];
	if( s[k-1] == 'S' )
	{
	BFS[bfs_num][0] = i;
	BFS[bfs_num][1] = j;
	BFS[bfs_num][2] = k;
	BFS[bfs_num][3] = 0;
	label[i][j][k] = 1;
	bfs_num++;
	}
	}
	}
	int n;
	int answer = 0;
	for( n = 0 ; n < bfs_num ; n++ )
	{
	i = BFS[n][0];
	j = BFS[n][1];
	k = BFS[n][2];
	int minute = BFS[n][3];
	if( map[i+1][j][k] == 'E' ||
	map[i-1][j][k] == 'E' ||
	map[i][j+1][k] == 'E' ||
	map[i][j-1][k] == 'E' ||
	map[i][j][k+1] == 'E' ||
	map[i][j][k-1] == 'E' )
	{
	answer = minute+1;
	break;
	}
	if( map[i+1][j][k] == '.' && !(label[i+1][j][k]) )
	{
	BFS[bfs_num][0] = i+1;
	BFS[bfs_num][1] = j;
	BFS[bfs_num][2] = k;
	BFS[bfs_num][3] = minute+1;
	label[i+1][j][k] = 1;
	bfs_num++;
	}
	if( map[i-1][j][k] == '.' && !(label[i-1][j][k]) )
	{
	BFS[bfs_num][0] = i-1;
	BFS[bfs_num][1] = j;
	BFS[bfs_num][2] = k;
	BFS[bfs_num][3] = minute+1;
	label[i-1][j][k] = 1;
	bfs_num++;
	}
	if( map[i][j+1][k] == '.' && !(label[i][j+1][k]) )
	{
	BFS[bfs_num][0] = i;
	BFS[bfs_num][1] = j+1;
	BFS[bfs_num][2] = k;
	BFS[bfs_num][3] = minute+1;
	label[i][j+1][k] = 1;
	bfs_num++;
	}
	if( map[i][j-1][k] == '.' && !(label[i][j-1][k]) )
	{
	BFS[bfs_num][0] = i;
	BFS[bfs_num][1] = j-1;
	BFS[bfs_num][2] = k;
	BFS[bfs_num][3] = minute+1;
	label[i][j-1][k] = 1;
	bfs_num++;
	}
	if( map[i][j][k+1] == '.' && !(label[i][j][k+1]) )
	{
	BFS[bfs_num][0] = i;
	BFS[bfs_num][1] = j;
	BFS[bfs_num][2] = k+1;
	BFS[bfs_num][3] = minute+1;
	label[i][j][k+1] = 1;
	bfs_num++;
	}
	if( map[i][j][k-1] == '.' && !(label[i][j][k-1]) )
	{
	BFS[bfs_num][0] = i;
	BFS[bfs_num][1] = j;
	BFS[bfs_num][2] = k-1;
	BFS[bfs_num][3] = minute+1;
	label[i][j][k-1] = 1;
	bfs_num++;
	}
	}
	if( answer )
	printf( "Escaped in %d minute(s).\n", answer );
	else
	printf( "Trapped!\n" );
	}
	return 0;
	}

view raw UVa532.c hosted with ❤ by GitHub