3. JOI 2023 - Painting
JOI đang chơi với một phần mềm vẽ. Phần mềm cho phép vẽ trên một bảng ô vuông hình chữ nhật gồm \(H\) hàng và \(W\) cột. Mỗi ô có một màu, được biểu diễn bằng một số nguyên từ \(1\) đến \(10^9\).
Gọi ô ở hàng thứ \(i\) từ trên xuống (\(1 \le i \le H\)), cột thứ \(j\) từ trái sang (\(1 \le j \le W\)) là ô \((i, j)\). Hiện tại, màu của ô \((i, j)\) là \(A_{i,j}\).
Ta gọi vùng của ô \((i, j)\) là tập hợp các ô có thể đi đến từ ô \((i, j)\) bằng cách liên tục di chuyển sang một ô chung cạnh, mà không đi vào ô có màu khác với ô \((i, j)\).
Phần mềm có chức năng tô màu vùng. Khi chọn một ô \((x, y)\) (\(1 \le x \le H\), \(1 \le y \le W\)) và một màu \(c\) (\(1 \le c \le 10^9\)), chức năng này đổi màu của tất cả các ô thuộc vùng của ô \((x, y)\) thành \(c\).
JOI chọn một ô \((x, y)\) và một màu \(c\), rồi sử dụng chức năng tô màu vùng đúng một lần với ô và màu đã chọn. Điểm số của JOI là số ô thuộc vùng của ô \((x, y)\) sau khi tô màu.
Hãy tìm điểm số lớn nhất mà JOI có thể đạt được.
Dữ liệu vào
Dữ liệu vào có dạng:
H W
A_{1,1} A_{1,2} ... A_{1,W}
A_{2,1} A_{2,2} ... A_{2,W}
...
A_{H,1} A_{H,2} ... A_{H,W}
Dữ liệu ra
In trên một dòng điểm số lớn nhất mà JOI có thể đạt được.
Ràng buộc
- \(1 \le H \le 500\).
- \(1 \le W \le 500\).
- \(1 \le A_{i,j} \le 10^9\) (\(1 \le i \le H\), \(1 \le j \le W\)).
- Tất cả các giá trị trong dữ liệu vào đều là số nguyên.
Chấm điểm
- \(9\) điểm: \(H = 1\).
- \(32\) điểm: \(H \le 30\), \(W \le 30\), \(A_{i,j} \le 5\) với mọi \(1 \le i \le H\), \(1 \le j \le W\).
- \(18\) điểm: \(H \le 30\), \(W \le 30\).
- \(10\) điểm: \(A_{i,j} \le 2\) với mọi \(1 \le i \le H\), \(1 \le j \le W\).
- \(31\) điểm: Không có ràng buộc bổ sung.
Ví dụ
Ví dụ 1
Input
4 4
1 2 3 1
2 2 3 1
1 2 3 1
3 3 2 2Output
9Giải thích
Ban đầu, vùng của ô \((2, 2)\) gồm bốn ô \((1, 2)\), \((2, 1)\), \((2, 2)\) và \((3, 2)\). Vì vậy, nếu chọn ô \((2, 2)\) và màu \(3\) để tô màu vùng, màu của bốn ô này sẽ đổi thành \(3\) như hình dưới đây.
Sau khi tô màu, vùng của ô \((2, 2)\) gồm chín ô \((1, 2)\), \((1, 3)\), \((2, 1)\), \((2, 2)\), \((2, 3)\), \((3, 2)\), \((3, 3)\), \((4, 1)\) và \((4, 2)\). Do đó, JOI đạt \(9\) điểm.
Không thể đạt từ \(10\) điểm trở lên, nên in ra \(9\).
Ví dụ này thỏa mãn ràng buộc của các bài toán con \(2, 3, 5\).
Ví dụ 2
Input
2 10
1 2 2 1 3 3 3 3 1 1
1 1 1 1 1 1 1 3 3 3Output
18Giải thích
Ví dụ này thỏa mãn ràng buộc của các bài toán con \(2, 3, 5\).
Ví dụ 3
Input
5 5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1Output
25Giải thích
Ví dụ này thỏa mãn ràng buộc của các bài toán con \(2, 3, 4, 5\).
Nguồn
Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc, hình minh họa và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.