你的v[sr][sc] = true;v数组没有再次更新
> #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行） (89) einstein17 2010-04-23 22:28:44