#include <iostream>
#include <queue>
using namespace std;

struct Position
{
	int r, c, s;
	Position( int x, int y, int z )
		:r( x ), c( y ), s( z ){};
	Position(){}
};

int l_process();
int r_process();
int bfs();

queue<Position> q;
int sr, sc, er, ec;
int w, h;
char maze[40][40];
bool v[40][40];
const int move[4][2] = { 0, -1, -1, 0, 0, 1, 1, 0 };

int main()
{
	int c, i, j;
	scanf( "%d", &c );
	while ( c-- )
	{
		scanf( "%d%d", &w, &h );
		char ctemp;
		for ( i = 0; i < h; ++i )
		{
			scanf( "%c", &ctemp );
			for ( j = 0; j < w; ++j )
			{
				scanf( "%c", &maze[i][j] );
				if ( maze[i][j] == 'S' )
					sr = i, sc = j;
				if ( maze[i][j] == 'E' )
					er = i, ec = j;
			}
		}
		cout << l_process() << ' ' << r_process() << ' ' << bfs() << endl;
	}
	return 0;
}

int l_process()
{
	int state;
	if ( sr == h - 1 )
		state = 0;
	else if ( sc == 0 )
		state = 1;
	else if ( sr == 0 )
		state = 2;
	else if ( sc == w - 1 )
		state = 3;
	int step = 1, rt = sr, ct = sc;
	while ( maze[rt][ct] != 'E' )
	{
		if ( maze[rt + move[state][0]][ct + move[state][1]] == '.' )
		{
			++step;
			rt += move[state][0];
			ct += move[state][1];
			state = ( state + 3 ) % 4;
			continue;
		}
		while ( !( maze[rt + move[state][0]][ct + move[state][1]] == '#' && maze[rt + move[( state + 1 ) % 4][0]][ct + move[( state + 1 ) % 4][1]] == '.' ))
		{
			if ( maze[rt + move[state][0]][ct + move[state][1]] == 'E' )
			{
				return ++step;
			}
			state = ( state + 1 ) % 4;
		}
		++step;
		rt += move[( state + 1 ) % 4][0];
		ct += move[( state + 1 ) % 4][1];
	}
	return step;
}

int r_process()
{
	int state;
	if ( sr == h - 1 )
		state = 0;
	else if ( sc == 0 )
		state = 1;
	else if ( sr == 0 )
		state = 2;
	else if ( sc == w - 1 )
		state = 3;
	int step = 1, rt = sr, ct = sc;
	while ( maze[rt][ct] != 'E' )
	{
		if ( maze[rt + move[( state + 2 ) % 4][0]][ct + move[( state + 2 ) % 4][1]] == '.' )
		{
			++step;
			rt += move[( state + 2 ) % 4][0];
			ct += move[( state + 2 ) % 4][1];
			state = ( state + 1 ) % 4;
			continue;
		}
		while ( !( maze[rt + move[( state + 2 ) % 4][0]][ct + move[( state + 2 ) % 4][1]] == '#' && maze[rt + move[( state + 1 ) % 4][0]][ct + move[( state + 1 ) % 4][1]] == '.' ))
		{
			if ( maze[rt + move[( state + 2 ) % 4][0]][ct + move[( state + 2 ) % 4][1]] == 'E' )
			{
				return ++step;
			}
			state = ( state + 3 ) % 4;
		}
		++step;
		rt += move[( state + 1 ) % 4][0];
		ct += move[( state + 1 ) % 4][1];
	}
	return step;
}

int bfs()
{
	while ( !q.empty())
		q.pop();
	memset( v, 0, sizeof v );
	q.push( Position( sr, sc, 1 ));
	v[sr][sc] = true;
	int row, col, i;
	Position pos;
	while ( !q.empty())
	{
		pos = q.front();
		q.pop();
		for ( i = 0; i < 4; ++i )
		{
			row = pos.r + move[i][0];
			col = pos.c + move[i][1];
			if ( row >= 0 && row < h && col >= 0 && col < w )
			{
				if ( maze[row][col] == 'E' )
					return ++pos.s;
				if ( maze[row][col] == '.' )
				{
					q.push( Position( row, col, pos.s + 1 ));
				}
			}
		}
	}
	return -1;
}

• Re:循环+BFS～为什么TLE 帮忙看看（152行） (3482) einstein17 2010-04-23 22:23:26
  • Re:循环+BFS～为什么TLE 帮忙看看（152行） (89) einstein17 2010-04-23 22:28:44