| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
能找到的数据都测试了,可是提交还是错,求测试数据啊,附代码求解答#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&¤tnode.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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator