Trong một mảnh vườn hình chữ nhật có các cạnh m, n nguyên dương người ta trồng cà rốt trong những ô vuông đơn vị có cạnh 1. Trong mảnh vườn này có một chú thỏ ở trong một cái hang chiếm diện tích 1 ô vuông đơn vị. Chú thỏ cần xác định miền người ta đã trồng cà rốt có diện tích lớn nhất trong mảnh vườn để đào một đường hầm ngắn nhất đi qua các ô vuông chung cạnh từ hang đến miền diện tích lớn nhất đó. (Miền được hiểu là hình gồm một hoặc nhiều ô vuông đơn vị chung cạnh. Hai miền khác nhau không có một cạnh ô vuông nào chung).
Dữ liệu:
• 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, dòng thứ i 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ả:
• Dòng đầu ghi S là chiều dài của đường hầm (S=0 nếu hang thỏ đang ở trên miề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 miền diện tích lớn nhất trồng cà rốt.
TEST CASE 1
ĐẦU VÀO
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
ĐẦU RA
4
1 1
1 2
1 3
1 4
1 5
Bình luận