'''simple docstring'''




def __lowerCAmelCase			(							UpperCamelCase__    ,  UpperCamelCase__    ,  UpperCamelCase__    )     ->   int:

    def update_area_of_max_square(UpperCamelCase__    ,  UpperCamelCase__    ) -> int:
        # BASE CASE
        if row >= rows or col >= cols:
            return 0

        __lowerCamelCase          =  update_area_of_max_square(UpperCamelCase__    ,  col + 1    )
        __lowerCamelCase          =  update_area_of_max_square(row + 1    ,  col + 1    )
        __lowerCamelCase          =  update_area_of_max_square(row + 1    ,  UpperCamelCase__    )

        if mat[row][col]:
            __lowerCamelCase          =  1 + min([right, diagonal, down]    )
            __lowerCamelCase          =  max(largest_square_area[0]    ,  UpperCamelCase__    )
            return sub_problem_sol
        else:
            return 0

    __lowerCamelCase          =  [0]
    update_area_of_max_square(0    ,  0    )
    return largest_square_area[0]






def __lowerCAmelCase			(							UpperCamelCase__    ,  UpperCamelCase__    ,  UpperCamelCase__    )     ->   int:

    def update_area_of_max_square_using_dp_array(
        UpperCamelCase__    ,  UpperCamelCase__    ,  UpperCamelCase__    ) -> int:
        if row >= rows or col >= cols:
            return 0
        if dp_array[row][col] != -1:
            return dp_array[row][col]

        __lowerCamelCase          =  update_area_of_max_square_using_dp_array(UpperCamelCase__    ,  col + 1    ,  UpperCamelCase__    )
        __lowerCamelCase          =  update_area_of_max_square_using_dp_array(row + 1    ,  col + 1    ,  UpperCamelCase__    )
        __lowerCamelCase          =  update_area_of_max_square_using_dp_array(row + 1    ,  UpperCamelCase__    ,  UpperCamelCase__    )

        if mat[row][col]:
            __lowerCamelCase          =  1 + min([right, diagonal, down]    )
            __lowerCamelCase          =  max(largest_square_area[0]    ,  UpperCamelCase__    )
            __lowerCamelCase          =  sub_problem_sol
            return sub_problem_sol
        else:
            return 0

    __lowerCamelCase          =  [0]
    __lowerCamelCase          =  [[-1] * cols for _ in range(UpperCamelCase__    )]
    update_area_of_max_square_using_dp_array(0    ,  0    ,  UpperCamelCase__    )

    return largest_square_area[0]






def __lowerCAmelCase			(							UpperCamelCase__    ,  UpperCamelCase__    ,  UpperCamelCase__    )     ->   int:
    __lowerCamelCase          =  [[0] * (cols + 1) for _ in range(rows + 1    )]
    __lowerCamelCase          =  0
    for row in range(rows - 1    ,  -1    ,  -1    ):
        for col in range(cols - 1    ,  -1    ,  -1    ):
            __lowerCamelCase          =  dp_array[row][col + 1]
            __lowerCamelCase          =  dp_array[row + 1][col + 1]
            __lowerCamelCase          =  dp_array[row + 1][col]

            if mat[row][col] == 1:
                __lowerCamelCase          =  1 + min(UpperCamelCase__    ,  UpperCamelCase__    ,  UpperCamelCase__    )
                __lowerCamelCase          =  max(dp_array[row][col]    ,  UpperCamelCase__    )
            else:
                __lowerCamelCase          =  0

    return largest_square_area






def __lowerCAmelCase			(							UpperCamelCase__    ,  UpperCamelCase__    ,  UpperCamelCase__    )     ->   int:
    __lowerCamelCase          =  [0] * (cols + 1)
    __lowerCamelCase          =  [0] * (cols + 1)
    __lowerCamelCase          =  0
    for row in range(rows - 1    ,  -1    ,  -1    ):
        for col in range(cols - 1    ,  -1    ,  -1    ):
            __lowerCamelCase          =  current_row[col + 1]
            __lowerCamelCase          =  next_row[col + 1]
            __lowerCamelCase          =  next_row[col]

            if mat[row][col] == 1:
                __lowerCamelCase          =  1 + min(UpperCamelCase__    ,  UpperCamelCase__    ,  UpperCamelCase__    )
                __lowerCamelCase          =  max(current_row[col]    ,  UpperCamelCase__    )
            else:
                __lowerCamelCase          =  0
        __lowerCamelCase          =  current_row

    return largest_square_area


if __name__ == "__main__":
  import doctest

  doctest.testmod()
  print(largest_square_area_in_matrix_bottom_up(2, 2, [[1, 1], [1, 1]]))

'''simple docstring'''




def __lowerCAmelCase			(							UpperCamelCase__    )     ->   str:
    return "".join(chr(ord(UpperCamelCase__    ) - 32    ) if '''a''' <= char <= '''z''' else char for char in word    )


if __name__ == "__main__":
  from doctest import testmod

  testmod()
