[PTNK - TS10 - 2024] Bài 2: San lấp
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Bản đồ một vùng đất là một hình chữ nhật kích thước ~m \times n~ được chia làm lưới ô vuông đơn vị, các hàng của lưới được đánh số từ ~1~ tới ~m~ từ trên xuống dưới và các cột của lưới được đánh số từ ~1~ tới ~n~ từ trái qua phải. Ô nằm trên giao của hàng ~x~, cột ~y~ được gọi là ô ~(x, y)~, mỗi ô có hai trạng thái là ô nước hay ô đất. Bản đồ được mô tả bởi bảng ~h(m \times n)~ với ~h_{xy} = 1~ nếu ô ~(x, y)~ là đất và ~h_{xy} = 0~ nếu ô ~(x, y)~ là nước.
Những ô đất tạo thành những "đảo" định nghĩa như sau: Hai ô đất gọi là cùng đảo nếu ta có thể đi từ ô này tới ô kia bằng cách di chuyển qua các ô kề cạnh là đất, ngược lại hai ô đó được coi là nằm trên hai đảo khác nhau.
Yêu cầu: Bạn được phép lấp đúng ~1~ ô nước để trở thành ô đất (tức là đổi giá trị một ô ~0~ thành ~1~) sao cho sau khi lấp thì nhận được một đảo có diện tích lớn nhất có thể.
Input
- Dòng ~1~ chứa hai số nguyên dương ~m, n \le 1000~.
- ~m~ dòng tiếp theo, dòng thứ ~i~ chứa ~n~ số, số thứ ~j~ là ~h_{ij} = 0~ hoặc ~1~. Các số trên một dòng của input file được ghi cách nhau ít nhất một dấu cách. Dữ liệu đảm bảo trên bản đồ có ít nhất một ô bằng ~0~.
Output
- Ghi ra một số nguyên duy nhất là số ô của đảo lớn nhất nhận được sau khi lấp một ô.
Sample Input 1
6 6
1 0 1 0 1 1
1 0 1 0 1 1
1 1 1 0 0 0
0 0 0 1 1 1
1 1 0 0 1 0
1 1 1 0 1 1
Sample Output 1
14
Bình luận