Time Limit: 1000MS Memory Limit: 32768KB 64bit IO Format: %I64d & %I64u

Description

You find yourself trapped in a large rectangular room, made up of large square tiles; some are accessible, others are blocked by obstacles or walls. With a single step, you can move from one tile to another tile if it is horizontally or vertically adjacent (i.e. you cannot move diagonally).
To shake off any people following you, you do not want to move in a straight line. In fact, you want to take a turn at every opportunity, never moving in any single direction longer than strictly necessary. This means that if, for example, you enter a tile from the south, you will turn either left or right, leaving to the west or the east. Only if both directions are blocked, will you move on straight ahead. You never turn around and go back!
Given a map of the room and your starting location, figure out how long it will take you to escape (that is: reach the edge of the room).

 

Input

On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test case:

a line with two integers separated by a space, h and w (1 <= h, w <= 80), the height and width of the room;

then h lines, each containing w characters, describing the room. Each character is one of . (period; an accessible space), # (a blocked space) or @ (your starting location).
There will be exactly one @ character in each room description.

 

Output

For each test case:

A line with an integer: the minimal number of steps necessary to reach the edge of the room, or -1 if no escape is possible.

 

Sample Input

2

9 13

#############

#@……….#

#####.#.#.#.#

#………..#

#.#.#.#.#.#.#

#.#…….#.#

#.#.#.#.#.#.#

#………..#

#####.#######

4 6

#.####

#.#.##

#…@#

######

 

 

 

Sample Output

31

-1

 

Source

bapc2007_pre


思路:BFS,不能简单认为每个点只能走一次,而是每个点只能从每个方向走一次,所以vis数组要多一维来存储方向。题目意思是只要能拐弯就拐弯,否则直走,不能后退(ps. 你TM是傻b么,出口在前面还拐弯)。存储方向的时候保证一条直线上的方向的奇偶性一致,扩展的时候模2就知道当前扩展到的方向跟原来是不是一条线了,否则还要挨个判断,太麻烦。

AC代码:

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
int h, w;
char map[85][85];
const int dx[] = {0, 1, 0, -1},
			dy[] = {1, 0, -1, 0};
bool vis[85][85][5];
struct node
{
	int x, y, step, dir;
};
node start;
queue <node> q;
void input()
{
	scanf("%d%d", &h, &w);
	for (int i = 0; i < h; i++)
		scanf("%s", map[i]);
}
void pre()
{
	for (int i = 0; i < h; i++)
		for (int j = 0; j < w; j++)
			if (map[i][j] == '@')
				start.x = i, start.y = j;
	start.step = 0;
	start.dir = -1;
	memset(vis, 0, sizeof(vis));
	while (!q.empty())
		q.pop();
}
void bfs()
{
	pre();
    q.push(start);
    while (!q.empty())
	{
		bool flag;
		node u = q.front();
		q.pop();
		if (u.x == 0 || u.x == h - 1 || u.y == 0 || u.y == w - 1)
		{
			printf("%d\n", u.step);
			return;
		}
		node next;
		next.step = u.step + 1;
		for (int i = 0; i < 4; i++)
		{
			next.x = u.x + dx[i];
			next.y = u.y + dy[i];
			if (vis[u.x][u.y][i] || map[next.x][next.y] == '#')
				continue;
			flag = 0;
			if (i % 2 == u.dir % 2)
			{
				if (i != u.dir)
					continue;
                if (i % 2 == 0 && map[u.x + 1][u.y] == '#' && map[u.x - 1][u.y] == '#')
					flag = 1;
                if (i % 2 == 1 && map[u.x][u.y + 1] == '#' && map[u.x][u.y - 1] == '#')
					flag = 1;
			}
			else
				flag = 1;
			if (!flag)
				continue;
			vis[u.x][u.y][i] = 1;
			next.dir = i;
			q.push(next);
		}
	}
	printf("-1\n");
}
int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		input();
		bfs();
	}
	return 0;
}

 

分类: ACM/ICPC

发表评论

电子邮件地址不会被公开。 必填项已用*标注