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

int head, front, rear, temp;
int que[40000];
char map[200][200];
int row, col;
int Row[200], Col[200];
int R, C;
int begin_i, begin_j, end_i, end_j;
int visit[200][200];
int sum;

int dfs_left(int row, int col)
{
	//cout << row << col << endl;
	//if(row < 0 || col < 0 || row >= R || col >= C || map[row][col] == '#')
		//return 0;
	if(map[row][col] == 'E')
		return sum;
X:	if(head == 1) {
		if((map[row - 1][col] != '#' && map[row][col - 1] == '#') || (map[row - 1][col] != '#' && visit[row][col - 1] == 1)) {
			visit[row][col] = 1;
			sum ++;
			return dfs_left(row - 1, col);
		}
		else
			head = 2;
	}
	if(head == 2) {
		if((map[row][col - 1] != '#' && map[row + 1][col] == '#') || (map[row][col - 1] != '#' && visit[row + 1][col] == 1)) {
			visit[row][col] = 1;
			sum ++;
			return dfs_left(row, col - 1);
		}
		else
			head = 3;
	}
	if(head == 3) {
		if((map[row + 1][col] != '#' && map[row][col + 1] == '#') || (map[row + 1][col] != '#' && visit[row][col + 1] == 1)) {
			visit[row][col] = 1;
			sum ++;
			return dfs_left(row + 1, col);
		}
		else
			head = 4;
	}
	if(head == 4) {
		if((map[row][col + 1] != '#' && map[row - 1][col] == '#') || (map[row][col + 1] != '#' && visit[row - 1][col] == 1)) {
			visit[row][col] = 1;
			sum ++;
			return dfs_left(row, col + 1);
		}
		else {
			head = 1;
			goto X;
		}
	}
	
}

int dfs_right(int row, int col)
{
	//cout << row << col << endl;
	//if(row < 0 || col < 0 || row >= R || col >= C || map[row][col] == '#')           //为什么不能加这句 很郁闷
		//return 0;
	if(map[row][col] == 'E')
		return sum;
X:	if(head == 4) {
		if((map[row][col + 1] != '#' && map[row + 1][col] == '#') || (map[row][col + 1] != '#' && visit[row + 1][col] == 1)) {
			visit[row][col] = 1;
			sum ++;
			return dfs_right(row, col + 1);
		}
		else 
			head = 3;
	}
	if(head == 3) {
		if((map[row + 1][col] != '#' && map[row][col - 1] == '#') || (map[row + 1][col] != '#' && visit[row][col - 1] == 1)) {
			visit[row][col] = 1;
			sum ++;
			return dfs_right(row + 1, col);
		}
		else
			head = 2;
	}
	if(head == 2) {
		if((map[row][col - 1] != '#' && map[row - 1][col] == '#') || (map[row][col - 1] != '#' && visit[row - 1][col] == 1)) {
			visit[row][col] = 1;
			sum ++;
			return dfs_right(row, col - 1);
		}
		else
			head = 1;
	}
	if(head == 1) {
		if((map[row - 1][col] != '#' && map[row][col + 1] == '#') || (map[row - 1][col] != '#' && visit[row][col + 1] == 1)) {
			visit[row][col] = 1;
			sum ++;
			return dfs_right(row - 1, col);
		}
		else {
			head = 4;
			goto X;
		}
	}
	
	
}

int main()          //shortest 在主函数里求
{
	int N;
	int i, j;
	int move[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

	cin >> N;
	while(N --) {
		cin >> C >> R;
		for(i = 0; i < R; i ++)
			for(j = 0; j < C; j ++)
				cin >> map[i][j];
		for(i = 0; i < R; i ++)
			for(j = 0; j < C; j ++) 
				if(map[i][j] == 'S') {
					begin_i = i;
					begin_j = j;
				}

		memset(visit, 0, sizeof(visit));
		memset(Row, 0, sizeof(Row));
		memset(Col, 0, sizeof(Col));
		memset(que, 0, sizeof(que));
		front = rear = 0;
		que[rear ++] = 0;
		Row[0] = begin_i;
		Col[0] = begin_j;
		visit[begin_i][begin_j] = 1;
		while(front < rear) {
			temp = front ++;           //天呐 BUG了这么久 就因为写成temp = rear ++
			if(map[Row[temp]][Col[temp]] == 'E')
				break;
			for(i = 0; i < 4; i ++) {
				row = Row[temp] + move[i][0];
				col = Col[temp] + move[i][1];
				if(row >= 0 && col >= 0 && row < R && col < C && visit[row][col] == 0 && map[row][col] != '#') {
					visit[row][col] = 1;
					Row[rear] = row;
					Col[rear] = col;
					que[rear ++] = que[temp] + 1;
					//cout << row << "XXX" <<col << endl;
				}
			}
		}
		memset(visit, 0, sizeof(visit));
		sum = 0;
		head = 1;		
		cout << dfs_left(begin_i, begin_j) + 1 <<" ";

		memset(visit, 0, sizeof(visit));
		sum = 0;
		head = 1;
		cout<< dfs_right(begin_i, begin_j) + 1 <<" ";
		//cout << dfs_left(); //<< " " << right() << " " << que[temp] + 1 << endl;	
		cout << que[temp] + 1 << endl;
	}
	return 0;
}

• 深搜+广搜 怎么会TLE啊。。。。 (0) 4053040 2010-02-12 19:55:35