Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

能找到的数据都测试了,可是提交还是错,求测试数据啊,附代码求解答

Posted by kimi940211 at 2014-03-20 18:22:54 on Problem 2049
#include<iostream>
#include<queue>
using namespace std;

struct node
{
	int x, y, dir;
};
int path[300][300];
int direction[4][2] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
int map[300][300][4];
int x, y, dir, t;
int w, d;
node beginnode, aimnode,currentnode,nextnode;

void BFS()
{
	queue<node> q;
	beginnode.dir = -1;
	path[beginnode.x][beginnode.y] = 0;
	q.push(beginnode);
	while (!q.empty())
	{
		currentnode = q.front();
		q.pop();
		if (currentnode.x == aimnode.x&&currentnode.y == aimnode.y)continue;
		for (int i = 0; i < 4; i++)
		{
			nextnode.x = currentnode.x + direction[i][0];
			nextnode.y = currentnode.y + direction[i][1];
			if (nextnode.x<200 && nextnode.y<200 && nextnode.x>=0 && nextnode.y>=0 && currentnode.dir != i&&map[currentnode.x][currentnode.y][i] != 2)
			{
				int door = path[currentnode.x][currentnode.y];
				if (map[currentnode.x][currentnode.y][i] == 1)
				{
					door++;
				}
				if (door < path[nextnode.x][nextnode.y])
				{
					path[nextnode.x][nextnode.y] = door;
					nextnode.dir = (i+2)%4;
					q.push(nextnode);
				}
			}
		}
	}
}

int main()
{
	while (cin >> w >> d&&!(w == -1 && d == -1))
	{
		for (int i = 0; i < 200; i++)
		{
			for (int j = 0; j < 200; j++)
			{
				path[i][j] = 10000;
				map[i][j][0] = map[i][j][1] = map[i][j][2] = map[i][j][3] = 0;
			}
		}
		aimnode.x = 0;
		aimnode.y = 0;
		for (int i = 1; i <= w; i++)
		{
			cin >> x >> y >> dir >> t;
			for (int j = 1; j <= t; j++)
			{
				if (dir == 0)
				{
					map[x + j][y][0] = 2;
					map[x + j][y + 1][2] = 2;
				}
				if (dir == 1)
				{
					map[x][y + j][1] = 2;
					map[x + 1][y + j][3] = 2;
				}
			}
		}
		for (int i = 1; i <= d; i++)
		{
			cin >> x >> y >> dir;
			if (dir == 0)
			{
				map[x + 1][y][0] = 1;
				map[x + 1][y + 1][2] = 1;
			}
			if (dir == 1)
			{
				map[x][y + 1][1] = 1;
				map[x + 1][y + 1][3] = 1;
			}
		}
		float beginx, beginy;
		cin >> beginx >> beginy;
		if (beginx >= 200 || beginy >= 200 || beginx <= 0 || beginy <= 0)cout << "0" << endl;
		else
		{
			beginx++;
			beginy++;
			beginnode.x = beginx;
			beginnode.y = beginy;
			BFS();
			if (path[aimnode.x][aimnode.y] != 10000)cout << path[aimnode.x][aimnode.y] << endl;
			else cout << "-1" << endl;
		}
	}
	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator