//
you're reading...
Bài tập huấn luyện, Chủ đề đồ thị (Graph)

Bài tập huấn luyện: Thỏ và cà rốt

[Bộ đề huấn luyện về chủ đề đồ thị]


Chuyên đề Đồ thị (Graph) – Bài 11


Đề bài


Trong một mảnh vườn hình chữ nhật có cạnh m, n người ta trồng cà rốt trong những ô đơn vị hình vuông có cạnh 1. Trong mảnh vườn này có một chú thỏ ở trong một hang chiếm diện tích 1 ô vuông đơn vị, chú thỏ này cần xác định niền người ta đã trồng cà rốt có diện tích (Hai miền khác nhau không có một cạnh ô vuông nào chung) lớn nhất trong mảnh vườn để đào một đường hầm ngắn nhất theo phương dọc hoặc phương ngang từ hang đến phần diện tích lớn nhất đó.

Dữ liệu vào từ file văn bản Tho.INP.

  • Dòng đầu tiên ghi 4 số M , N , x, y với x, y là hàng và cột của hang thỏ trong mảnh vườn (1 <= M,N <= 100).
  • Trong M dòng tiếp theo, mỗi dòng có N ký tự 0 hoặc 1 thể hiện hàng thứ i của mảnh vườn với ý nghĩa 0 là không trồng cà rốt, 1 là có trồng cà rốt.

Kết quả: Ghi ra file văn bản Tho.OUT:

  • Dòng đầu ghi S là chiều dài của đường hầm (S=0 nếu hang thỏ đang ở trên phần trồng cà rốt có diện tích lớn nhất
  • Nếu S>0 thì trong các dòng tiếp theo lần lượt ghi hàng và cột của các ô trên đường hầm bắt đầu từ hang thỏ đến vùng diện tích lớn nhất trồng cà rốt

Ví dụ:

CAROT.INP CAROT.OUT
6 6 1 1

0 0 0 0 1 1

0 0 0 0 1 1

0 0 0 0 1 1

0 0 0 0 1 1

0 0 0 0 1 1

1 1 1 0 0 0

4

1 1

1 2

1 3

1 4

1 5

 

 


Hướng dẫn


[]


Chương trình


[]

Advertisements

About pascalteacher

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

Thảo luận

Không có bình luận

Trả lờ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 Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

Các tác giả

Categories

Tháng Mười Hai 2016
H B T N S B C
« Th11   Th1 »
 1234
567891011
12131415161718
19202122232425
262728293031  

NCT Computer

Flickr Photos

Thống kê

  • 149,868 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: