#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/*
Sample Input

2
8 8
########
#......#
#.####.#
#.####.#
#.####.#
#.####.#
#...#..#
#S#E####
9 5
#########
#.#.#.#.#
S.......E
#.#.#.#.#
#########

Sample Output

37 5 5
17 17 9
 */
#define QSIZE 2000
char nodes[1600];
int visit_table[1600];

int queue[QSIZE];
int head = 0;
int rear = 0;

int dequeue()
{
	return queue[head++ % QSIZE];
}

void enqueue(int value)
{
	queue[rear++ % QSIZE] = value;
}

int empty()
{
	return rear == head;
}

int main()
{
//      char *maze = "##########.#.#.#.#S.......E#.#.#.#.##########";
	int case_num;
	int w, h, i;
	int total;
	int start;
	int step = 1;
	int curr_rear;
	int curr_pos;
	//0:left 1:up 2:right 3:down
	// l:(direction+delta)%4
	// r:(direction-delta+6)%4
	int direction[] = { 0, -1, -0, 1 };
	// l:(direction+delta)%4
	// r:(direction-delta+6)%4
	int new_direction[] = { 3, 0, 1, 2 };
	int curr_d = 0, start_d;
	scanf("%d", &case_num);
//      case_num = 1;
	while (case_num--) {
		scanf("%d %d", &w, &h);
//              w = 9;
//              h = 5;
		total = w * h;
		direction[0] = w;
		direction[2] = -w;
		for (i = 0; i < total; i++) {
			nodes[i] = getchar();
			if (nodes[i] == '\n')
				nodes[i] = getchar();
//                     nodes[i] = maze[i];
			if (nodes[i] == 'S') {
				start = i;
				enqueue(i);
			}
		}
		if (start < w)
			start_d = 3;
		else if (start > total - w)
			start_d = 1;
		else if (start % w == 0)
			start_d = 2;
		else
			start_d = 0;
		//left
		curr_pos = start;
		curr_d = start_d;
		while (nodes[curr_pos] != 'E') {
			int tmp, delta;
//                      printf("%d,",curr_pos);
			delta = direction[curr_d % 4];
			tmp = curr_pos + delta;
			if (nodes[tmp] != '#') {
				curr_pos = tmp;
				curr_d = new_direction[curr_d % 4];
				step++;
				continue;
			}
			delta = direction[(curr_d + 1) % 4];
			tmp = curr_pos + delta;
			if (nodes[tmp] != '#') {
				curr_pos = tmp;
				curr_d = new_direction[(curr_d + 1) % 4];
				step++;
				continue;
			}
			delta = direction[(curr_d + 2) % 4];
			tmp = curr_pos + delta;
			if (nodes[tmp] != '#') {
				curr_pos = tmp;
				curr_d = new_direction[(curr_d + 2) % 4];
				step++;
				continue;
			}
			delta = direction[(curr_d + 3) % 4];
			tmp = curr_pos + delta;
			if (nodes[tmp] != '#') {
				curr_pos = tmp;
				curr_d = new_direction[(curr_d + 3) % 4];
				step++;
				continue;
			}
		}
		printf("%d ", step);
		step = 1;

		//right
		curr_d = start_d;
		curr_pos = start;
		while (nodes[curr_pos] != 'E') {
			int tmp, delta;
			delta = direction[(curr_d + 6) % 4];
			tmp = curr_pos + delta;
			if (nodes[tmp] != '#') {
				curr_pos = tmp;
				curr_d = new_direction[(curr_d + 6) % 4];
				step++;
				continue;
			}
			delta = direction[(curr_d + 5) % 4];
			tmp = curr_pos + delta;
			if (nodes[tmp] != '#') {
				curr_pos = tmp;
				curr_d = new_direction[(curr_d + 5) % 4];
				step++;
				continue;
			}
			delta = direction[(curr_d + 4) % 4];
			tmp = curr_pos + delta;
			if (nodes[tmp] != '#') {
				curr_pos = tmp;
				curr_d = new_direction[(curr_d + 4) % 4];
				step++;
				continue;
			}
			delta = direction[(curr_d + 3) % 4];
			tmp = curr_pos + delta;
			if (nodes[tmp] != '#') {
				curr_pos = tmp;
				curr_d = new_direction[(curr_d + 3) % 4];
				step++;
				continue;
			}

		}
		printf("%d ", step);
		step = 1;

		//min
		memset(visit_table, 0, 1600);
		visit_table[start] = 1;
		while (1) {
			curr_rear = rear;
			while (head != curr_rear) {
				int value = dequeue();
//                              printf("%d\n",value);
				if (nodes[value] == 'E')
					goto done;
				if ((value - w >= 0) && nodes[value - w] != '#'
				    && !visit_table[value - w]) {
					enqueue(value - w);
					visit_table[value - w] = 1;
				}
				if ((value + w) < total
				    && nodes[value + w] != '#'
				    && !visit_table[value + w]) {
					enqueue(value + w);
					visit_table[value + w] = 1;
				}
				if (nodes[value - 1] != '#'
				    && !visit_table[value - 1]) {
					enqueue(value - 1);
					visit_table[value - 1] = 1;
				}
				if (nodes[value + 1] != '#'
				    && !visit_table[value + 1]) {
					enqueue(value + 1);
					visit_table[value + 1] = 1;
				}
			}
			step++;
		}
 done:
		printf("%d\n", step);
		head = rear = 0;
		step = 1;
	}
	exit(0);
}

• Re:为什么老是TLE啊，感觉好像死循环了，但是一直都找不出来哪里有错 (4) chhaya 2010-06-30 17:04:15