Bài 4. Dịch chuyển tức thời (4 điểm)
Trong một trò chơi di chuyển trên bảng số có quy tắc như sau:
• Bảng số gồm có 𝑁 dòng và 𝑀 cột; các dòng được đánh số 1 đến 𝑁, từ trên xuống dưới; các cột
được đánh số từ 1 đến 𝑀, từ trái sang phải. Ô ở dòng thứ 𝑢 giao với cột thứ 𝑣 được gọi là ô
(𝑢, 𝑣). Ô (𝑢, 𝑣) chứa một số nguyên 𝐴 %& không âm.
• Từ ô (𝑢, 𝑣) , người chơi có thể di chuyển sang một ô có chung cạnh: (𝑢 − 1, 𝑣), (𝑢 +
1, 𝑣), (𝑢, 𝑣 − 1), (𝑢, 𝑣 + 1) hoặc di chuyển sang một ô khác có cùng giá trị và không thể di
chuyển vào ô có giá trị bằng 0. Mỗi lần di chuyển tốn một đơn vị thời gian.
Yêu cầu: Cho vị trí ô xuất phát và ô đích, tìm thời gian nhỏ nhất đi từ ô xuất phát về ô đích theo luật của
trò chơi.
Dữ liệu vào từ tệp BAI4.INP:
• Dòng đầu tiên gồm hai số nguyên dương 𝑁 và 𝑀 là số dòng và số cột của bảng.
• Dòng thứ hai gồm bốn số 𝑥, 𝑦, 𝑧, 𝑡 mô tả xuất phát ở ô (𝑥, 𝑦) và đích ở ô (𝑧, 𝑡).
• 𝑁 dòng sau, mỗi dòng gồm 𝑀 số nguyên không âm mô tả bảng số.
Kết quả ra ghi vào tệp BAI4.OUT:
Gồm một số nguyên dương là số đơn vị thời gian nhỏ nhất để đi từ ô xuất phát đến ô đích thoả
mãn yêu cầu.
Trang 2/3
Ví dụ:
BAI4.INP BAI4.OUT Giải thích
5 4
9 Có thể đi như các đỉnh được tô đậm: 1, 2, 3, 4, 6, 9, 8, 10, 13, 14.
1 1 5 4
1 2 3 4
1 2 3 4
5 0 0 6
5 0 0 6
7 0 8 9
7 0 8 9
0 0 10 0
0 0 10 0
11 12 13 14
11 12 13 14
4 Có thể đi như các đỉnh được tô đậm: 1, 5, 7, 7, 9.
1 2 3 4
5 0 0 6
7 0 8 6
7 0 8 6
0 0 6 0
0 0 6 0
3 4 7 9
3 4 7 9
Lưu ý: Mỗi số nguyên cách nhau một dấu cách. Dữ liệu đảm bảo luôn có đường đi từ xuất phát đến
đích.
• Có 40% số test: 𝑁, 𝑀 ≤ 100, 𝐴 %& < 10 ! và các số nguyên dương trong bảng phân biệt;
• Có 20% số test khác: 𝑁, 𝑀 ≤ 1000, 𝐴 %& < 10 ! và các số nguyên dương trong bảng phân biệt;
• Có 20% số test khác: 𝑁, 𝑀 ≤ 1000, 𝐴 %& < 10 ! và các số nguyên dương trong bảng lặp lại không
quá hai lần;
• Có 20% số test còn lại: 𝑁, 𝑀 ≤ 1000, 𝐴 %& < 10 ! và các số trong bảng có thể lặp lại nhiều lần.
Bạn đang xem bài 4. - Đề thi học sinh giỏi môn Tin học lớp 12 cấp thành phố năm 2020-2021 - Sở GD&ĐT Hà Nội (Đề số 3)
