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