Hình chữ nhật có chu vi lớn nhất

Bối cảnh

Trong một bản đồ lưới, ban tổ chức muốn dựng một tuyến kiểm tra hình chữ nhật dọc theo các ô biên của một vùng. Mỗi hình chữ nhật được xác định bởi hai hàng top < bottom và hai cột left < right; do đó cả chiều cao và chiều rộng đều ít nhất 2. Điểm của hình chữ nhật là tổng giá trị chỉ trên chu vi, không tính các ô nằm hoàn toàn bên trong.

Nhiệm vụ là tìm hình chữ nhật có tổng chu vi lớn nhất. Nếu có nhiều hình cùng tổng, chọn bộ tọa độ (top,left,bottom,right) nhỏ nhất theo thứ tự duyệt lexicographic: top nhỏ hơn, rồi left, rồi bottom, rồi right.

Đây là bài Hard theo phong cách Olympic ở mức nền tảng: số hình chữ nhật là O(r²c²), và với B12 bạn chưa học 2D prefix hoặc kỹ thuật tối ưu chu vi. Giới hạn ma trận nhỏ để cho phép brute force có tổ chức, nhưng người làm phải kiểm soát 4 biên và tránh cộng bốn góc hai lần.

Điểm khó là tổ chức không gian bốn chỉ số và tính đúng chu vi cho mỗi ứng viên.

Yêu cầu

1. Duyệt mọi top,left,bottom,right hợp lệ.
2. Cộng hai cạnh ngang đầy đủ.
3. Cộng hai cạnh dọc nhưng bỏ hàng top/bottom để tránh đếm góc lần hai.
4. Cập nhật max; thứ tự vòng lặp tự giữ tie lexicographic.

Input

Dòng 1: rows cols; sau đó ma trận.

Output

Một dòng maxPerimeter top left bottom right.

Ràng buộc

2 ≤ rows,cols ≤ 30, |a[i][j]| ≤ 10^9.

Ví dụ 1

Input

3 3
1 2 3
4 5 6
7 8 9

Output

40 0 0 2 2

Giải thích

Ta phải chọn hình chữ nhật có chiều cao và chiều rộng ít nhất 2, rồi chỉ cộng các ô trên chu vi. Với toàn ma trận 3×3, chu vi gồm tám ô ngoài cùng và có tổng 1+2+3+4+6+7+8+9 = 40; ô giữa 5 không được tính. Các hình chữ nhật 2×2 hoặc 2×3/3×2 đều có chu vi nhỏ hơn 40 trong dữ liệu này. Vì vậy hình tối ưu là từ góc trên trái (0,0) đến góc dưới phải (2,2), cho output 40 0 0 2 2.

Ví dụ 2

Input

2 2
1 2
3 4

Output

10 0 0 1 1

Giải thích

Ma trận 2×2 chỉ tạo được một hình chữ nhật hợp lệ có hai hàng và hai cột: toàn bộ ma trận. Với kích thước 2×2, cả bốn ô đều nằm trên chu vi, tổng bằng 1+2+3+4 = 10. Tọa độ hai góc là (0,0) và (1,1), nên kết quả 10 0 0 1 1.

Thông tin học tập

• Module: M03
• Buổi: B12
• Loại bài: ADVANCED
• Độ khó: Hard
• Concepts: 2D static arrays, rectangle enumeration, border sum, brute force optimization, lexicographic tie-break
• Giới hạn kiến thức: B01-B12
• Time limit: 1 second(s)
• Memory limit: 256 MB
• Point: 100