Nagyerdő là một khu rừng hình vuông nằm ở thành phố Debrecen, được mô hình hóa bằng một lưới ô vuông kích thước \(N \times N\). Các hàng của lưới được đánh số từ \(0\) đến \(N-1\) từ bắc xuống nam, và các cột được đánh số từ \(0\) đến \(N-1\) từ tây sang đông. Gọi ô nằm ở hàng \(r\) và cột \(c\) của lưới là ô \((r,c)\).

Trong khu rừng, mỗi ô hoặc trống hoặc chứa một cây. Có ít nhất một ô trống trong khu rừng.

DVSC, câu lạc bộ thể thao nổi tiếng của thành phố, đang có kế hoạch xây dựng một sân vận động bóng đá mới trong khu rừng. Một sân vận động có kích thước \(s\) (với \(s \ge 1\)) là một tập gồm \(s\) ô trống khác nhau \((r_0,c_0),\ldots,(r_{s-1},c_{s-1})\). Một cách chính xác:

• với mỗi \(i\) từ \(0\) đến \(s-1\) (kể cả hai đầu), ô \((r_i,c_i)\) là trống;
• với mỗi \(i,j\) mà \(0 \le i < j < s\), ít nhất một trong hai điều kiện \(r_i \ne r_j\) và \(c_i \ne c_j\) thỏa mãn.

Bóng đá được chơi bằng cách sử dụng một quả bóng di chuyển qua các ô của sân vận động. Một cú sút thẳng được định nghĩa là một trong hai hành động sau:

• Di chuyển quả bóng từ ô \((r,a)\) đến ô \((r,b)\) (\(0 \le r,a,b < N\), \(a \ne b\)), trong đó sân vận động chứa tất cả các ô giữa hai ô \((r,a)\) và \((r,b)\) trong hàng \(r\). Một cách chính xác:
• nếu \(a < b\) thì sân vận động phải chứa ô \((r,k)\) với mỗi \(k\) thỏa mãn \(a \le k \le b\);
• nếu \(a > b\) thì sân vận động phải chứa ô \((r,k)\) với mỗi \(k\) thỏa mãn \(b \le k \le a\).
• Di chuyển quả bóng từ ô \((a,c)\) đến ô \((b,c)\) (\(0 \le c,a,b < N\), \(a \ne b\)), trong đó sân vận động chứa tất cả các ô giữa hai ô \((a,c)\) và \((b,c)\) trong cột \(c\). Một cách chính xác:
• nếu \(a < b\) thì sân vận động phải chứa ô \((k,c)\) với mỗi \(k\) thỏa mãn \(a \le k \le b\);
• nếu \(a > b\) thì sân vận động phải chứa ô \((k,c)\) với mỗi \(k\) thỏa mãn \(b \le k \le a\).

Một sân vận động là chuẩn nếu có thể di chuyển quả bóng từ ô bất kì trong sân vận động đến bất kì ô nào khác trong sân vận động với tối đa \(2\) cú sút thẳng. Lưu ý rằng bất kì sân vận động nào có kích thước \(1\) đều là sân vận động chuẩn.

Ví dụ, xét một khu rừng có kích thước \(N=5\), với các ô \((1,0)\) và \((4,2)\) chứa cây và mọi ô khác đều trống. Hình dưới đây mô tả ba sân vận động có thể có. Các ô chứa cây được tô tối, các ô thuộc sân vận động có sọc.

Sân vận động bên trái là chuẩn. Tuy nhiên, sân vận động ở giữa không chuẩn, vì cần ít nhất \(3\) cú sút thẳng để di chuyển quả bóng từ ô \((4,1)\) đến \((4,3)\). Sân vận động bên phải cũng không chuẩn, vì không thể di chuyển quả bóng từ ô \((3,0)\) đến \((1,3)\) bằng các cú sút thẳng.

Câu lạc bộ thể thao muốn xây dựng một sân vận động chuẩn càng lớn càng tốt. Nhiệm vụ của bạn là tìm giá trị lớn nhất của \(s\) sao cho tồn tại một sân vận động chuẩn có kích thước \(s\) trong khu rừng.

Chi tiết cài đặt

Bạn cần cài đặt hàm sau:

int biggest_stadium(int N, std::vector<std::vector<int>> F);

• \(N\): kích thước khu rừng.
• \(F\): một mảng kích thước \(N\) mà mỗi phần tử là một mảng kích thước \(N\), mô tả các ô trong khu rừng. Với mỗi \(r,c\) thỏa mãn \(0 \le r < N\) và \(0 \le c < N\), \(F[r][c]=0\) nghĩa là ô \((r,c)\) trống, và \(F[r][c]=1\) nghĩa là ô chứa cây.
• Hàm cần trả về kích thước lớn nhất của sân vận động chuẩn có thể xây dựng trong khu rừng.
• Hàm được gọi đúng một lần với mỗi test.

Ví dụ

Xét lời gọi hàm sau:

biggest_stadium(5, [[0, 0, 0, 0, 0],
                    [1, 0, 0, 0, 0],
                    [0, 0, 0, 0, 0],
                    [0, 0, 0, 0, 0],
                    [0, 0, 1, 0, 0]])

Trong ví dụ này, khu rừng được mô tả ở bên trái và một sân vận động chuẩn với kích thước \(20\) được mô tả ở bên phải của hình dưới đây:

Do không có sân vận động chuẩn nào có kích thước \(21\) hoặc lớn hơn nên hàm cần trả về \(20\).

Các ràng buộc

• \(1 \le N \le 2\,000\).
• \(0 \le F[i][j] \le 1\) (với mỗi \(i,j\) sao cho \(0 \le i < N\) và \(0 \le j < N\)).
• Có ít nhất một ô trống trong khu rừng. Nói cách khác, \(F[i][j]=0\) với một cặp \(i,j\) nào đó thỏa mãn \(0 \le i < N\) và \(0 \le j < N\).

Các subtask

Trong mỗi subtask, bạn có thể đạt được \(25\%\) số điểm của subtask nếu chương trình của bạn xác định chính xác liệu tập gồm tất cả các ô trống có phải là một sân vận động chuẩn hay không.

Chính xác hơn, đối với mỗi test trong đó tập gồm tất cả các ô trống là một sân vận động chuẩn, lời giải của bạn:

• nhận được điểm tối đa nếu trả về câu trả lời đúng (là kích thước của tập gồm tất cả các ô trống);
• nhận được \(0\) điểm trong các trường hợp còn lại.

Đối với mỗi test trong đó tập gồm tất cả các ô trống không phải là một sân vận động chuẩn, lời giải của bạn:

• nhận được điểm tối đa nếu trả về câu trả lời đúng;
• nhận được \(0\) điểm nếu trả về kích thước của tập gồm tất cả các ô trống;
• nhận được \(25\%\) số điểm nếu trả về bất kì giá trị nào khác.

Điểm cho mỗi subtask là điểm thấp nhất trong các test của subtask đó.

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu vào theo định dạng sau:

dòng 1: N
dòng 2 + i (0 ≤ i < N): F[i][0] F[i][1] … F[i][N − 1]

Trình chấm mẫu ghi kết quả của bạn theo định dạng sau:

dòng 1: giá trị trả về của biggest_stadium

Nguồn: Olympic Tin học Quốc tế 2023 (IOI 2023). Bản dịch tiếng Việt chính thức của đoàn Việt Nam, được đối chiếu với đề tiếng Anh chính thức. Nội dung đề được phát hành theo giấy phép CC BY.