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

HDU 1253 3维bfs 一直wa,原来是小错误。

2013年10月21日 ⁄ 综合 ⁄ 共 1113字 ⁄ 字号 评论关闭

wa!!!教训 。continue的地方写成了return

#include <iostream>
#include <queue>
using namespace std;
int map[51][51][51];
int visit[51][51][51];
int a, b, c, step;
int dir[6][3] = {{1,0,0}, {-1,0,0}, {0,1,0},   
{0,-1,0}, {0,0,1}, {0,0,-1}};
struct node  
{  
	int x, y, z, step;  
};

int judge(int x, int y, int z)
{
	if(x >= 0 && x <a && y >= 0 && y < b && z >= 0 && z < c && map[x][y][z] == 0 && visit[x][y][z] == 0)
		return 1;
	return 0;
}

void bfs()
{
	int x, y, z;
	node cur, next;
	queue<node> q;
	cur.x = 0;
	cur.y = 0; 
	cur.z = 0; 
	cur.step = 0;

	q.push(cur);
	visit[0][0][0] = 1;
	if(a == 1 && b == 1 && c == 1)
	{
		printf("0\n");
		return;
	}

	while(!q.empty())
	{
		cur = q.front();
		q.pop();
		for(int i = 0; i < 6; i++)
		{
			next.x = x =  cur.x + dir[i][0];
			next.y = y =  cur.y + dir[i][1];
			next.z = z =  cur.z + dir[i][2];
			next.step = cur.step + 1;
			if(next.step > step)
				continue; //刚开始不小心写成了return,一直wa。放弃了。几天后不小心发现。血的教训啊
			if(judge(x, y, z))
			{
				visit[x][y][z] = 1;
				if(x == a - 1 && y == b - 1 && z == c - 1)
				{
					printf("%d\n", next.step);
					return;
				}
				q.push(next);
			}
		}
	}
	printf("-1\n");
}

int main()
{
	int t; 
	cin >> t;
	while(t--)
	{
		memset(map, 0, sizeof(map));
		memset(visit, 0, sizeof(visit));
		scanf("%d%d%d%d", &a, &b, &c, &step);
		for(int i = 0; i < a; i++)
			for(int j = 0; j < b; j++)
				for(int k = 0; k < c; k++)
					scanf("%d", &map[i][j][k]);
		if(a + b + c - 3 >  step) //剪枝,时间减半
		{
			cout << -1 << endl;
			continue;
		}
		bfs();
	}
	return 0;
}

抱歉!评论已关闭.