Bài tập Lập trình - Bài 4: Lập lịch di chuyển cho Robot
Bài tập lập trình 4: Lập lịch di chuyển cho Robot
1. Mô tả bài toán
Có hai con robot A và B di chuyển trên một đồ thị có trọng số G. Do cả hai robot đều được điều
khiển bởi sóng radio nên chúng không thể ở gần nhau trong khoảng cách r. Ban đầu hai robot
đứng ở đỉnh a và đỉnh b trên G. Robot tại a muốn di chuyển đến đỉnh c dọc theo một đường đi
trong G, và robot tại b muốn di chuyển đến đỉnh d. Việc di chuyển này có thể mô ta dưới dạng
việc lập lịch di chuyển: tại mỗi thời điểm, lịch di chuyển xác định chỉ một robot di chuyển qua
một cạnh, từ một đỉnh tới một hàng xóm; cuối cùng, robot từ đỉnh a nên ở đỉnh c, và robot từ b
nên ở đỉnh d.
Một lịch di chuyển gọi là không gây nhiễu nếu không có thời điểm nào mà hai robot lại đứng ở
Bạn hãy viết chương trình nhập vào một đồ thị có trọng số G, hai đỉnh bắt đầu a và b, hai đỉnh
kết thúc c và d, và tham số r > 0. Thông báo ra màn hình một lịch di chuyển nếu có; nếu không
có thông báo ’Không thể!’.
Input:
• Dòng đầu tiên là số đỉnh n < 100 và số cạnh m của đồ thị G.
• m dòng tiếp theo mỗi dòng gồm 3 số x y w thể hiện: Đồ thị G có cạnh {x, y} với trọng
số w.
• dòng tiếp theo chứa bốn số a b c d là đỉnh bắt đầu và kết thúc của hai robot.
• dòng cuối cùng là số r > 0.
Output: Bao gồm nhiều dòng, mỗi dòng là hai số u v thể hiện các đỉnh mà hai robot đứng tại
mỗi thời điểm trong lịch di chuyển.
Ví dụ: Xét đồ thị dưới đây với các đỉnh bắt đầu a = 0, b = 2; các đỉnh kết thúc c = 2, d = 3; và
r = 4. Ta có một lịch di chuyển được chỉ ra ở dưới đây. Khoảng cách cặp đỉnh được chỉ ra ở cột
cuối để chứng minh rằng đây là một lịch di chuyển không gây nhiễu.
1
1
2
6
1
2
5
Lịch di chuyển khoảng cách
0 2
0 3
1 3
2 3
7
5
8
7
7
7
9
0
5
4
3
4
Nếu ta thay r trong ví dụ trên bằng 5, thì không có lịch di chuyển không nhiễu nào cả.
1
khoảng cách là độ dài đường đi ngắn nhất
1
2
2. Một số dữ liệu Test
Dữ liệu Test 1
10 12
0 4 10
0 9 11
1 4 9
2 6 5
2 8 1
3 4 11
3 6 5
4 5 2
5 7 9
7 8 3
7 9 10
8 9 4
1 3
// n m
Lịch di chuyển khoảng cách
1 3
20
1 4
1 0
4 0
3 0
3 4
9
19
10
21
11
// a b
// c d
// r
3 4
7
4
3
11
9
5
1
6
2
10
5
0
5
9
11
7
9
10
1
4
3
2
8
Hình 1. Đồ thị của dữ liệu Test 1
3
Dữ liệu Test 2
15 22
// n m
0 8 11
0 11 7
1 4 15
1 7 13
2 3 2
2 4 12
2 8 10
2 10 13
2 12 6
2 13 13
5 8 5
5 9 14
6 7 2
6 8 7
6 11 5
6 14 3
7 9 11
8 12 7
9 12 9
10 12 15
11 12 7
11 14 8
1 3
Lịch di chuyển khoảng cách
1 3
7 3
6 3
6 2
6 4
8 4
2 4
3 4
29
21
19
17
29
22
12
14
// a b
// c d
// r
3 4
7
4
Dữ liệu Test 3
15 23
0 2 3
// n m
0 9 6
0 10 11
1 9 5
2 4 15
2 5 14
2 7 1
2 9 5
2 11 6
2 12 14
3 6 7
3 11 7
3 12 10
3 13 14
3 14 14
4 8 2
Lịch di chuyển khoảng cách
1 3
1 12
9 12
9 4
2 4
12 4
3 4
23
19
14
10
15
8
18
4 12 11
5 13 15
6 11 2
8 9 8
8 12 6
8 14 11
10 12 3
1 3
3 4
7
// a b
// c d
// r
5
2
12
4
13
13
15
6
1
2
10
12
13
3
7
15
8
5
5
7
10
9
13
11
7
14
11
7
9
8
5
11
0
7
2
14
3
6
Hình 2. Đồ thị của dữ liệu Test 2
6
8
11
14
2
4
6
1
11
8
12
5
15
9
3
14
10
5
1
14
2
14
10
6
5
11
3
15
7
6
13
14
0
3
7
6
7
11
2
Hình 3. Đồ thị của Test 3
6 trang
17820
Free
Bạn đang xem tài liệu "Bài tập Lập trình - Bài 4: Lập lịch di chuyển cho Robot", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_tap_lap_trinh_bai_4_lap_lich_di_chuyen_cho_robot.pdf
