算法: 寻找最大良田正方形区域

Question

A farmer wants to farm their land with the maximum area where good land is present. The “land” is represented as a matrix with 1s and 0s, where 1s mean good land and 0s mean bad land. The farmer only want to farm in a square of good land with the maximum area. Please help the farmer to find the maximum area of the land they can farm in good land. Example:

[  
    ["0", "1", "1", "0", "1"],  
    ["1", "1", "0", "1", "0"],  
    ["0", "1", "1", "1", "0"],  
    ["1", "1", "1", "1", "0"],  
    ["1", "1", "1", "1", "1"],  
    ["0", "0", "0", "0", "0"]  
]

Output: 9

Solution

At first, we should think, if one inputList item’s top,left and diagonal is 1, it can consist as a square, once one of them is 0, it can not be a square(because question asked us, square must consisted with 1).

It is a dynamic programing question.

At first, we create a new list which the length and width is the same as the inputList.

rows, cols = len(nums), len(nums[0])
dp = [[0] * cols for _ in range(rows)]

We should start with the inputList far left and topside(we use i,j for index).

if i==0 or j==0, and if the inputList[i][j]==1, the dp item should be 1, because nothing in their left, top or diagonal.

for i in range(rows):
    for j in range(cols):
        if nums[i][j] == "1":
            if i == 0 or j == 0:
                dp[i][j] = 1

if one dp item’s top, left, and diagonal is 1, the item should be 2.

But when the dp item’s top, left, and diagonal is 2, which means the item’s top’s top, left’s left and diagonal’s diagonal is also 1, the item can be part of a larger square, assign dp[i][j] as 2.

But sometimes the dp item’s top is 2, left is 3, and the diagonal is 3, it means, the two items in the top is also 1, three item in the left is also 1, three items in the diagonal is 1, we should get the minimum of that, because square but not rectangle.

dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1

We should always update our max_side_length after assign dp

max_side = max(max_side, dp[i][j])

So the final solution is

class Solution:
    def maxSquares(self, nums: List[List[str]]) -> int:
        rows, cols = len(nums), len(nums[0])
        dp = [[0] * cols for _ in range(rows)]
        max_side = 0
        for i in range(rows):
            for j in range(cols):
                if nums[i][j] == "1":
                    if i == 0 or j == 0:
                        dp[i][j] = 1
                    else:
                        dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
                max_side = max(max_side, dp[i][j])
            for z in dp:
                print(z)
            print("______________")
        return max_side ** 2
if __name__ == '__main__':
    binary_list = [
        ["0", "1", "1", "0", "1"],
        ["1", "1", "0", "1", "0"],
        ["0", "1", "1", "1", "0"],
        ["1", "1", "1", "1", "0"],
        ["1", "1", "1", "1", "1"],
        ["0", "0", "0", "0", "0"]
    ]
    print(Solution().maxSquares(binary_list))

Question#

Solution#

Question

Solution