To solve this problem, we need to find the area of the largest 1-bordered square in a given grid of 0s and 1s. A 1-bordered square is defined as a square where all cells on its perimeter are 1s.

Approach

1. Auxiliary Matrices: Compute two auxiliary matrices, left and up, to store the number of consecutive 1s ending at each cell to the left and upwards, respectively. This helps in quickly checking if the borders of a potential square are all 1s.

   • left[i][j]: Number of consecutive 1s ending at (i, j) in the left direction (including the cell itself).
   • up[i][j]: Number of consecutive 1s ending at (i, j) in the upward direction (including the cell itself).

2. Check Valid Squares: For each cell (i, j) that is a 1, consider it as the bottom-right corner of a square. The maximum possible side length of the square starting from this cell is the minimum of left[i][j] and up[i][j]. For each possible side length from this maximum down to the current largest valid side length, check if the top row and left column of the square are all 1s using the auxiliary matrices.

3. Compute Area: The area of the largest valid square is the square of its side length.

Solution Code

def largest1BorderedSquare(grid):
    if not grid or not grid[0]:
        return 0

    m = len(grid)
    n = len(grid[0])

    # Compute left matrix
    left = [[0]*n for _ in range(m)]
    for i in range(m):
        left[i][0] = 1 if grid[i][0] == 1 else 0
        for j in range(1, n):
            if grid[i][j] == 1:
                left[i][j] = left[i][j-1] + 1
            else:
                left[i][j] = 0

    # Compute up matrix
    up = [[0]*n for _ in range(m)]
    for j in range(n):
        up[0][j] = 1 if grid[0][j] == 1 else 0
        for i in range(1, m):
            if grid[i][j] == 1:
                up[i][j] = up[i-1][j] + 1
            else:
                up[i][j] = 0

    max_side = 0

    for i in range(m):
        for j in range(n):
            if grid[i][j] == 1:
                current_max = min(left[i][j], up[i][j])
                if current_max <= max_side:
                    continue
                # Check from largest possible k down to max_side+1
                for k in range(current_max, max_side, -1):
                    top_row = i - k + 1
                    if top_row < 0:
                        continue
                    if left[top_row][j] < k:
                        continue
                    left_col = j - k + 1
                    if left_col < 0:
                        continue
                    if up[i][left_col] < k:
                        continue
                    # Found valid square of size k
                    max_side = k
                    break

    return max_side * max_side

Explanation

1. Auxiliary Matrices: The left matrix helps in checking if the bottom row of a square is all 1s, and the up matrix helps in checking if the right column of a square is all 1s.
2. Validity Check: For each cell, we check if the top row (using left matrix) and left column (using up matrix) of the potential square are all 1s. This ensures that all four borders of the square are 1s.
3. Efficiency: The approach efficiently reduces the number of checks needed by using the auxiliary matrices, making it faster than a brute-force approach. The time complexity is O(mnk), where k is the maximum possible side length of the square, which is manageable for typical grid sizes.

This solution effectively finds the largest 1-bordered square and returns its area. It handles all edge cases, including empty grids and grids with no valid squares.

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