现在的位置: 首页 > 综合 > 正文

HDU 1072 BFS

2013年10月06日 ⁄ 综合 ⁄ 共 911字 ⁄ 字号 评论关闭
#include <iostream>
#include <queue>
using namespace std;

struct node
{
	int x, y, time, step;
};

int map[20][20];
int n, m, sx, sy, dx, dy;
queue<node> que;
node now, next1;
int dir[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};

int BFS()
{
	now.x = sx;
	now.y = sy;
	now.time = 6;
	now.step = 0;
	while(!que.empty())
		que.pop();
	que.push(now);
	while(!que.empty())
	{
		now = que.front();
		que.pop();
		if(now.x == dx && now.y == dy && now.time > 0)
			return now.step;
		for(int i = 0; i < 4; i++)
		{
			next1.x = now.x + dir[i][0];
			next1.y = now.y + dir[i][1];
			next1.time = now.time - 1;
			next1.step = now.step + 1;

			if(next1.x >= 0 && next1.y >= 0 && next1.x < n && next1.y < m && map[next1.x][next1.y] != 0 && next1.time > 0)
			{
				if(map[next1.x][next1.y] == 4)
				{
					next1.time = 6;
					map[next1.x][next1.y] = 0;
				}
				que.push(next1);
			}
		}
	}
	return -1;
}

int main()
{
	freopen("1072.txt", "r", stdin);
	int T;
	scanf("%d", &T);
	while(T--)
	{
		scanf("%d%d", &n, &m);
		for(int i = 0; i < n; i++)
			for(int j = 0; j < m; j++)
			{
				scanf("%d", &map[i][j]);
				if(map[i][j] == 2)
				{
					sx = i;
					sy = j;
				}
				else if(map[i][j] == 3) //出口坐标
				{
					dx = i;
					dy = j;
				}
			}
		cout << BFS() << endl;
	}
	return 0;
}

抱歉!评论已关闭.