Hố đen
Tham khảoKotori
c_cpp
a year ago
2.5 kB
5
Indexable
#pragma warning (disable : 4996) #include<iostream> using namespace std; #define maxQ 10000000 class Point { public: int x, y; Point() { } Point(int a, int b) { x = a; y = b; } }; class hoden { public: Point A, B; int time; }; class Queue { Point d[maxQ]; int r, f; public: Queue() { r = f = -1; } void reset() { r = f = -1; } void enQ(Point v) { r++; d[r].x = v.x; d[r].y = v.y; } Point deQ() { return d[++f]; } bool isE() { return r == f; } }; int T, N; int map[1005][1005]; int Sx, Sy, Ex, Ey; Point Start, End; hoden hd[6]; int n, m; int visited[1005][1005]; int checkhoden[1005][1005]; int dx[4] = { -1, 0, 1, 0 }; int dy[4] = { 0, 1, 0, -1 }; Queue q; void init() { q.reset(); Start.x = Sx; Start.y = Sy; q.enQ(Start); for (int i = 0; i <= n; i++) { for (int j = 0; j <= n; j++) { map[i][j] = visited[i][j] = 0; checkhoden[i][j] = -1; } } for (int i = 0; i < N; i++) { checkhoden[hd[i].A.x][hd[i].A.y] = checkhoden[hd[i].B.x][hd[i].B.y] = hd[i].time; } map[Sx][Sy] = 1; } Point find_way(Point a) { for (int i = 0; i < N; i++) { if (a.x == hd[i].A.x && a.y == hd[i].A.y) { return hd[i].B; } else if(a.x == hd[i].B.x && a.y == hd[i].B.y) { return hd[i].A; } } return Point(-1,-1); } int bfs() { init(); while (!q.isE()) { Point a = q.deQ(); for (int i = 0; i < 4; i++) { int row = a.x + dx[i]; int col = a.y + dy[i]; if (row >= 0 && col >= 0 && row <= n && col <= n && map[row][col] == 0) { Point tmp(row, col); if (checkhoden[row][col] >= 0) { map[row][col] = map[a.x][a.y] + 1; Point new_way = find_way(tmp); map[new_way.x][new_way.y] = map[row][col] + checkhoden[row][col]; q.enQ(new_way); } else { map[row][col] = map[a.x][a.y] + 1; q.enQ(tmp); } } } } return map[Ex][Ey]; } int main() { //freopen("input.txt", "r", stdin); cin >> T; for (int tc = 1; tc <= T; tc++) { cin >> N; cin >> Sx >> Sy >> Ex >> Ey; for (int i = 0; i < N; i++) { cin >> hd[i].A.x >> hd[i].A.y >> hd[i].B.x >> hd[i].B.y >> hd[i].time; } n = (Sx > Ex) ? Sx : Ex; m = (Sy > Ey) ? Sy : Ey; n = (n > m) ? n : m; m = n; cout << "#" << tc << " "; int kq = bfs(); cout << kq - 1 << endl; } return 0; }
Editor is loading...
Leave a Comment