//
you're reading...
Bài tập huấn luyện

Bài tập huấn luyện: Robot cắt cỏ

Các cuộc thi robot diễn ra ngày càng sôi nổi ngay trong phạm vi Việt Nam. Sau bao nhiêu năm miệt mài với:

Chương trình = Cấu trúc dữ liệu + Thuật toán

các thành viên IOICamp quyết định bắt tay vào chế tạo robot. Khác với các robot trong các cuộc thi, họ muốn robot của mình phải có một sắc thái riêng. Sau nhiều lần thảo luận, các thành viên quyết định sẽ thiết kế một robot xén cỏ.

Giả định đồng cỏ là một lưới hình chữ nhật được chia thành các ô vuông đơn vị bởi M dòng được đánh số từ 1 đến M từ trên xuống dưới và N cột được đánh số từ 1 đến N từ trái sang phải. Mỗi ô vuông được gán một số tự nhiên là độ cao của cỏ tại ô đó (độ cao có thể bằng 0 tương ứng tại ô đó không có cỏ).

Để xén được cỏ thì robot có thể thực hiện các thao tác xén cỏ cơ bản, một thao tác xén cỏ gồm:

  1. Chọn vùng xén cỏ là một hình chữ nhật gồm một số ô vuông trên đồng cỏ. Do biết tận dụng các công nghệ cao, robot có thể tự điều chỉnh kích thước vùng xén cỏ.
  2. Đi xung quanh một vòng trên các ô biên của hình chữ nhật đã chọn và xén mọi cây cỏ ở các ô đã đi qua một đơn vị chiều cao. Tất cả các ô này đều phải có cỏ với độ cao lớn hơn 0 trước khi bị xén.

Sau một thời gian hoạt động, mặc dù nhận được rất nhiều đơn đặt hàng của các doanh nghiệp yêu mến nhưng chi phí cho robot vẫn là quá lớn. Nguyên nhân vì chương trình điều khiển robot quá yếu kém. Rất nhiều lần, lẽ ra để cắt một đồng cỏ, chỉ cần 5 hay 6 thao tác thì robot phải thực hiện tới 109 thao tác.

Để robot có thể hoạt động lâu dài có hiệu quả, Admin đề nghị các thành viên giải quyết bài toán sau: Cho trước một đồng cỏ, hãy tìm cho robot một dãy ít nhất thao tác để có thể cắt được toàn bộ cỏ của cánh đồng.

Input: ROBOT.INP

  • Dòng đầu tiên ghi 2 số nguyên dương M và N là kích thước của đồng cỏ.
  • Dòng thứ i trong M dòng tiếp theo ghi N số tự nhiên, số thứ j là độ cao của cỏ tại ô ở dòng i và cột j của đồng cỏ.

Output:            ROBOT.OUT

  • Dòng đầu tiên ghi số tự nhiên S là số thao tác robot cần thực hiện.
  • Dòng thứ k trong S dòng tiếp theo ghi 4 số nguyên X, Y, Z, T biểu diễn thông tin về một thao tác cắt cỏ với ý nghĩa vùng được chọn có ô trái trên ở dòng X, cột Y và ô phải dưới ở dòng Z, cột T.

Giới hạn:

  • 1 ≤ M, N ≤ 500
  • Độ cao của cỏ tại các ô không quá 100
  • Thời gian: 2 s/test
  • Bộ nhớ: 16 MB

Ví dụ:

ROBOT.INP ROBOT.OUT
4 4

1 1 1 0

1 1 2 0

1 2 2 0

0 0 0 1

3

1 1 3 3

2 2 3 3

4 4 4 4

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Tháng Mười 2016
M T W T F S S
« Sep   Nov »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

A bellezza di a natura (C☺rsica)

Southern White-faced Owl D75_5752.jpg

2016 Lake Yamanaka winter Fuji

More Photos

Thống kê

  • 78,768 lượt xem

%d bloggers like this: