Trong chương trình chinh phục mặt trăng, các
nhà khoa học đang chế tạo một con rô-bốt có thể di chuyển trên bề mặt của mặt
trăng. Một trong những bài kiểm tra đầu tiên của rô-bốt là di chuyển trên lưới
ô vuông có kích thước NxM (2≤N, M≤200) từ (1, 1) đến ô (N, M), các dòng được
đánh số từ 1 đến N, các cột được đánh số từ 1 đến M. Rô-bốt có thể di chuyển từ
ô này qua ô khác nếu hai ô chung cạnh. Trong những lần thử nghiệm đầu tiên
rô-bốt đều tìm được đường đi ngắn nhất để di chuyển, sau đó các nhà khoa học đã
đặt thêm K chướng ngại vật vào K ô khác nhau trên lưới, lúc này rô-bốt thường
đi thẳng vào các chướng ngại vật hoặc không thể tìm ra đường đi ngắn nhất.
Hãy giúp các nhà khoa học lập trình lại cho
rô-bốt để nó có thể di chuyển từ ô (1, 1) đến ô (N, M) theo con đường ngắn nhất
mà không va chạm với chướng ngại vật
Giả thiết ở ô (1, 1) và (N, M) không có chướng
ngại vật và luôn có ít nhất một đường đi
Dữ liệu vào: từ tệp
văn bản ROBOT1.INP
+ Dòng đầu tiên chứa 3 số nguyên dương N, M, K
+ K dòng tiếp theo mỗi dòng ghi 2 số nguyên u
và v cho biết tọa độ của một chướng ngại vật
Dữ liệu ra: ghi vào
tệp văn bản ROBOT1.OUT
+ Dòng đầu tiên ghi một số nguyên S cho biết số
bước đi ngắn nhất
+ S dòng tiếp theo mỗi dòng ghi tọa độ 1 ô cho
biết hành trình của rô bốt từ ô (1, 1) đến ô (N, M)
Ví dụ:
|
0
|
0
|
0
|
0
|
|
1
|
1
|
0
|
1
|
|
0
|
0
|
0
|
0
|
|
0
|
1
|
1
|
0
|
|
0
|
0
|
0
|
0
|
|
ROBOT1.INP
|
ROBOT1.OUT
|
|
5 4 5
2 1
2 2
2 4
4 2
4 3
|
8
1 1
1 2
1 3
2 3
3 3
3 4
4 4
5 4
|
Không có nhận xét nào:
Đăng nhận xét