Check frame around square is all 0s
frame_ok = True
# 1. Row above: i-1, columns j to j+k-1
for y in range(j, j +k):
if grid[i-1][y] !=0:
frame_ok = False
break
if not frame_ok:
continue
# 2. Row below: i +k, columns j to j+k-1
for y in range(j, j +k):
if grid[i +k][y] !=0:
frame_ok = False
break
if not frame_ok:
continue
#3. Column left: j-1, rows i to i+k-1
for x in range(i, i +k):
if grid[x][j-1] !=0:
frame_ok = False
break
if not frame_ok:
continue
#4. Column right: j +k, rows i to i+k-1
for x in range(i, i +k):
if grid[x][j +k] !=0:
frame_ok = False
break
if frame_ok:
# Found the largest possible area
print(k*k)
exit()
If no such square found
print(0)
Wait let's test this code against the example input: the input is 5x5 grid, and the code checks k=3 first (since n-2=3). Then i ranges from1 to (5-3-1)=1 → i=1, j=1. Check square (1-3,1-3): all1s → yes. Then check frame: row above (0, 1-3) → all 0s, row below (4, 1-3) → all0s, column left (1-3,0) → all0s, column right (1-3,4) → all0s → frame_ok is True, so output is3*3=9, which is correct.
Another test case: if n=3, then n-2=1, so k=1. Check i=1, j=1: square (1,1) must be1, and frame: row 0 (j=1) → 0; row2 (j=1) →0; column 0 (x=1) →0; column 2 (x=1) →0. If all those are true, then output is 1, else0.
This code should handle all cases correctly, and it's efficient enough for the problem's constraints. To solve this problem, we need to find the maximum number of 1's in a square that is completely surrounded by 0's in an n x n grid. The square must not touch the grid's boundaries and must be enclosed by 0's on all sides.
Approach
- Check Largest Squares First: We start with the largest possible square size (n-2, since the square must be at least one cell away from all grid edges) and work our way down to smaller squares. This ensures we find the maximum size quickly.
- Validate Square: For each square size, check all possible positions. A valid square must:
- Consist entirely of 1's.
- Be surrounded by 0's on all four sides (row above, row below, column left, column right).
Solution Code
n = int(input())
grid = []
for _ in range(n):
line = input().strip()
grid.append([int(c) for c in line])
max_area = 0
# Iterate from largest possible square size down to 1
for k in range(n-2, 0, -1):
max_i = n - k - 1
if max_i < 1:
continue # No valid positions for this k
# Check all possible top-left corners of the square
for i in range(1, max_i + 1):
for j in range(1, max_i + 1):
# Check if the square is all 1s
is_all_1 = True
for x in range(i, i + k):
for y in range(j, j + k):
if grid[x][y] != 1:
is_all_1 = False
break
if not is_all_1:
break
if not is_all_1:
continue
# Check if the frame around the square is all 0s
frame_valid = True
# Check row above the square
for y in range(j, j + k):
if grid[i-1][y] != 0:
frame_valid = False
break
if not frame_valid:
continue
# Check row below the square
for y in range(j, j + k):
if grid[i + k][y] != 0:
frame_valid = False
break
if not frame_valid:
continue
# Check column left of the square
for x in range(i, i + k):
if grid[x][j-1] != 0:
frame_valid = False
break
if not frame_valid:
continue
# Check column right of the square
for x in range(i, i + k):
if grid[x][j + k] != 0:
frame_valid = False
break
if frame_valid:
print(k * k)
exit()
# If no valid square found
print(0)
Explanation
- Reading Input: The grid is read as a list of lists of integers.
- Square Size Iteration: We start with the largest possible square size (n-2) and decrease the size until we find a valid square.
- Square Validation: For each square, we check if all cells are 1's. Then we check the surrounding frame (row above, row below, column left, column right) to ensure all cells are 0's.
- Output: The first valid square found (largest size) gives the maximum area, which is printed immediately. If no valid square is found, 0 is printed.
This approach efficiently finds the maximum size of the square surrounded by 0's by checking larger squares first, ensuring optimal performance for the given problem constraints. The complexity is O(n^3), which is feasible for n up to 100.

作者声明:本文包含人工智能生成内容。