H
hai6f2009
Chắc suất Đại học top - Giữ chỗ ngay!! ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.
CÂU HỎI 1: (7 điểm) Rô bốt gỡ mìn.
Trong cuộc chiến tại Afghanistan, để hạn chế thương vong cho các binh sĩ, người Mỹ đã áp dụng rất nhiều công nghệ hiện đại trong chiến tranh, một trong số đó là rô bốt gỡ mìn. Trước khi đưa vào sử dụng họ đã thử nghiệm trên một khu đất hình chữ nhật có diện tích MxN mét vuông. Khu đất được chia thành các ô vuông bằng nhau có diện tích 1 mét vuông, trong đó có 1 ô chứa mìn, một số ô có vật cản và đặt rô bốt vào một ô nào đó của khu đất. Trên màn hình ra đa của rô bốt phát hiện được vị trí có mìn và nhiệm vụ của rô bốt là phải di chuyển thật nhanh đến ô có mìn để gỡ.
Rô bốt có thể duy chuyển sang các ô chung cạnh hoặc chung góc với ô đang đứng nếu như ô đó không có vật cản và không vượt ra khỏi khu đất. Thời gian đi qua mỗi ô mất 1 giây, hãy tìm đường đi sao cho rô bốt đến được vị trí có mìn sớm nhất có thể.
Dữ liệu vào: Từ file văn bản ROBO.INP có cấu trúc như sau:
§ Dòng 1: chứa 2 số nguyên dương M, N ([TEX]2\leq M,N\leq 1000[/TEX]).
§ Dòng 2: chứa 4 số x1, y1, x2, y2 ; với x1, y1 là tọa độ của ô đặt rô bốt; x2, y2 là tọa độ của ô có mìn ([TEX]1\leq {x}_{1},{x}_{2} \leq M;1\leq {y}_{1},{y}_{2} \leq N[/TEX]).
§ Các dòng tiếp theo, dòng thứ i chứa 2 số xi, yi là tọa độ của ô có vật cản ([TEX]1\leq {x}_{i} \leq M, 1\leq {y}_{i} \leq N[/TEX]).
Dữ liệu ra: Ghi ra file văn bản ROBO.OUT một số nguyên duy nhất S là thời gian ít nhất để rô bốt đến được vị trí có mìn. Nếu không có đường đi thì ghi số -1.
Ví dụ:
ROBO.INP
5 5
1 1 5 5
1 3
2 2
3 2
2 4
4 4
ROBO.OUT
5
bài này mình nhờ là dùng thuật toán loang theo lớp nhưng mình lại quên cấu trúc thuật toán mất rồi! Mong các bạn giúp đỡ cho mình!
Trong cuộc chiến tại Afghanistan, để hạn chế thương vong cho các binh sĩ, người Mỹ đã áp dụng rất nhiều công nghệ hiện đại trong chiến tranh, một trong số đó là rô bốt gỡ mìn. Trước khi đưa vào sử dụng họ đã thử nghiệm trên một khu đất hình chữ nhật có diện tích MxN mét vuông. Khu đất được chia thành các ô vuông bằng nhau có diện tích 1 mét vuông, trong đó có 1 ô chứa mìn, một số ô có vật cản và đặt rô bốt vào một ô nào đó của khu đất. Trên màn hình ra đa của rô bốt phát hiện được vị trí có mìn và nhiệm vụ của rô bốt là phải di chuyển thật nhanh đến ô có mìn để gỡ.
Rô bốt có thể duy chuyển sang các ô chung cạnh hoặc chung góc với ô đang đứng nếu như ô đó không có vật cản và không vượt ra khỏi khu đất. Thời gian đi qua mỗi ô mất 1 giây, hãy tìm đường đi sao cho rô bốt đến được vị trí có mìn sớm nhất có thể.
Dữ liệu vào: Từ file văn bản ROBO.INP có cấu trúc như sau:
§ Dòng 1: chứa 2 số nguyên dương M, N ([TEX]2\leq M,N\leq 1000[/TEX]).
§ Dòng 2: chứa 4 số x1, y1, x2, y2 ; với x1, y1 là tọa độ của ô đặt rô bốt; x2, y2 là tọa độ của ô có mìn ([TEX]1\leq {x}_{1},{x}_{2} \leq M;1\leq {y}_{1},{y}_{2} \leq N[/TEX]).
§ Các dòng tiếp theo, dòng thứ i chứa 2 số xi, yi là tọa độ của ô có vật cản ([TEX]1\leq {x}_{i} \leq M, 1\leq {y}_{i} \leq N[/TEX]).
Dữ liệu ra: Ghi ra file văn bản ROBO.OUT một số nguyên duy nhất S là thời gian ít nhất để rô bốt đến được vị trí có mìn. Nếu không có đường đi thì ghi số -1.
Ví dụ:
ROBO.INP
5 5
1 1 5 5
1 3
2 2
3 2
2 4
4 4
ROBO.OUT
5
bài này mình nhờ là dùng thuật toán loang theo lớp nhưng mình lại quên cấu trúc thuật toán mất rồi! Mong các bạn giúp đỡ cho mình!
Last edited by a moderator: