Problem:
Largest Square Given a matrix ( H × W ) which contains only 1 and 0, find the area of the largest square matrix which only contains 0s. Input  H  W  c 1,1  c 1,2 ... c 1,W  c 2,1  c 2,2 ... c 2,W : c H,1  c H,2 ... c H,W  In the first line, two integers H and W separated by a space character are given. In the following H lines, c i , j , elements of the H × W matrix, are given. Output Print the area (the number of 0s) of the largest square. Constraints  1 ≤ H , W ≤ 1,400  Sample Input 4 5
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0
0 0 0 1 0 Sample Output 4

Solution (Python):
def read_tiles(h, w):
    c = []
    for _ in range(h):
        c.append([int(x) for x in input().split()])
    return c


def largest_square(h, w, c):
    ls = 0
    dp = [[None] * w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            if c[i][j] == 1:
                dp[i][j] = 0
            elif i == 0 or j == 0:
                dp[i][j] = 1
            else:
                dp[i][j] = (
                    min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
                )
            ls = max(ls, dp[i][j] ** 2)
    return ls

def main():
    h, w = map(int, input().split())
    c = read_tiles(h, w)
    print(largest_square(h, w, c))


main()

Solution (Python):
if __name__ == "__main__":
    H, W = map(lambda x: int(x), input().split())
    dp = [list(map(int, input().split())) for _ in range(H)]

    for h in range(H):
        for w in range(W):
            dp[h][w] ^= 1  

    for h in range(1, H):
        for w in range(1, W):
            if dp[h][w]:
                dp[h][w] = min(dp[h - 1][w - 1], dp[h - 1][w], dp[h][w - 1])
                dp[h][w] += 1

    print(max(w for h in dp for w in h) ** 2)

Solution (Python):


def solve():
    H, W = map(int, input().split())
    c = [list(map(int, input().split())) for _ in range(H)]
    dp = [[0] * (W+1) for _ in range(H+1)]

    ans = 0
    for i in range(1, H+1):
        for j in range(1, W+1):
            if c[i-1][j-1] == 1:
                dp[i][j] == 0
            else:
                dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                ans = max(ans, dp[i][j])

    print(ans**2)


if __name__ == "__main__":
    solve()

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

H,W=MAP()

grid = list2d(H+2, W+2, 0)
for i in range(1, H+1):
    row = LIST()
    for j in range(1, W+1):
        grid[i][j] = row[j-1]


dp=list2d(H+2, W+2, 0)
for i in range(1, H+1):
    for j in range(1, W+1):
        if grid[i][j]!=1:
            
            dp[i][j]=min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+1
mx=0
for i in range(1, H+1):
    mx=max(mx, max(dp[i]))
print(mx**2)

Solution (Python):
def solve(h, w, grid):
    dp = [[0]*w for i in range(h)]
    max_dp = 0

    for i in range(h):
        for j in range(w):
            if grid[i][j] == 1:
                dp[i][j] = 0
            else:
                if i - 1 < 0 or j - 1 < 0:
                    dp[i][j] = 1
                else:
                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
            max_dp = max(max_dp, dp[i][j])

    return max_dp * max_dp

h, w = map(int, input().split())
grid = [list(map(int, input().split())) for i in range(h)]
print(solve(h, w, grid))

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
Max = sys.maxsize
def ll():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def onem():
	return int(input())
def s(x):
	a = []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x):
	return " ".join(map(str,x))

h,w = m()

l = []

for i in range(h):
	a = ll()
	l.append(a)

dp = [[0 for i in range(w+1)] for j in range(h+1)]

for i in range(h):
	for j in range(w):
		if l[i][j] == 0:
			dp[i+1][j+1] = min(dp[i+1][j],dp[i][j+1],dp[i][j]) + 1
print(max(map(max,dp))**2)

Solution (Python):
h,w=map(int,input().split())
dp=[[0]*(w+1)]
table=str.maketrans('10','01')
for i in range(h):
    dp+=[[0]+list(map(int,input().translate(table).split()))]

P=[-1,-1,0]
Q=[-1,0,-1]
ans=0
for i in range(1,h+1):
    for j in range(1,w+1):
        if dp[i][j]==0:continue
        dp[i][j]=1+min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])
        ans=max(ans,dp[i][j])
print(ans*ans)

Solution (Python):
m = []
s = []
line = input()
h, w = list(map(int, line.split()))
s = [ [0] * w for _ in range(0, h)]
for _ in range(0, h):
    line = input()
    c = list(map(int, line.split()))
    m += [c]

def solve(h, w):
    ans = 0
    for y in range(0, h):
        for x in range(0, w):
            if m[y][x] == 1:
                s[y][x] = 0
            else:
                u = s[y - 1][x] if y > 0 else 0
                l = s[y][x - 1] if x > 0 else 0
                ul = s[y - 1][x - 1] if x > 0 and y > 0 else 0
                s[y][x] = 1 + min(u, l, ul)
            ans = max(ans, s[y][x])
    return ans * ans

ans = solve(h, w)
print(ans)

Solution (Python):
h, w = map(int, input().split())
c = [list(map(int, input().split())) for _ in range(h)]

dp = [[0 for _ in range(w)] for _ in range(h)]

for i in range(h):
    for j in range(w):
        if c[i][j]:
            dp[i][j] = 0
        else:
            dp[i][j] = 1

for i in range(h):
    for j in range(w):
        if c[i][j] == 1:
            dp[i][j] = 0
        elif i > 0 and j > 0:
            dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1

ans = 0
for i in range(h):
    ans = max(ans, max(dp[i]))
print(ans ** 2)

Solution (Python):
H, W = map(int, input().split())
c = []
for _ in range(H):
    *w, = map(int, input().split())
    c.append(w)

dp = []
for _ in range(H+2):
    dp.append([0]*(W+2))

ans = 0
for h in range(1, H+1):
    for w in range(1, W+1):
        if c[h-1][w-1] == 1:
            dp[h][w] = 0
        else:
            dp[h][w] = 1+min([
                dp[h-1][w-1],
                dp[h-1][w],
                dp[h][w-1]
            ])
            if ans < dp[h][w]:
                ans = dp[h][w]

print(ans**2)

Solution (Python):

"""
Created on Sat Jan  5 22:46:09 2019
DPL3A
@author: maezawa
"""
h, w = list(map(int,input().split()))
c = []
for _ in range(h):
    ci = list(map(int, input().split()))
    c.append(ci)

sq = [[0]*w for _ in range(h)]
for j in range(w):
    if c[0][j] == 1:
        sq[0][j] = 0
    else:
        sq[0][j] = 1
        
for i in range(h):
    if c[i][0] == 1:
        sq[i][0] = 0
    else:
        sq[i][0] = 1
        
if sq[0][0] == 1:
    maxsq = 1
else:
    maxsq = 0  
        
for i in range(1, h):
    for j in range(1, w):
        if c[i][j] == 1:
            sq[i][j] = 0
        else:
            thissq = min([sq[i-1][j], sq[i-1][j-1], sq[i][j-1]]) + 1
            sq[i][j] = thissq

for i in range(h):
    for j in range(w):
        maxsq = max([maxsq, sq[i][j]])
    
print(maxsq**2)

Solution (Python):
H, W = map(int, input().split())
S = [list(map(int, input().split())) for i in range(H)]
dp = [[0]*(W) for i in range(H)]

for i in range(H):
  for j in range(W):
    if S[i][j] == 0:
      dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])+1

print(max([max(a) for a in dp])**2)

Solution (Python):
h,w = map(int, input().split())
c = [list(map(int, input().split())) for i in range(h)]
dp = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    dp[i][0] = 1 if c[i][0] == 0 else 0
for i in range(w):
    dp[0][i] = 1 if c[0][i] == 0 else 0
for i in range(1,h):
    for j in range(1,w):
        if c[i][j] == 0:
            dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])+1
ans = 0
for i in dp:
    for j in i:
        ans = max(ans, j)
print(ans**2)

Solution (Python):
def getLargestSquare(H, W, G):
    maxWidth = 0
    dp = [[None] * W for i in range(H)]
    for i in range(H):
        for j in range(W):
            dp[i][j] = (G[i][j] + 1) % 2
            maxWidth |= dp[i][j]

    for i in range(1, H):
        for j in range(1, W):
            if G[i][j] == 1:
                dp[i][j] = 0
            else:
                dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
                maxWidth = max(maxWidth, dp[i][j])

    return maxWidth * maxWidth


if __name__ == '__main__':
    h, w = [int(v) for v in input().split()]
    c = []
    for i in range(h):
        c.append([int(v) for v in input().split()])

    print(getLargestSquare(h, w, c))

Solution (Python):
h,w=map(int,input().split(" "))
c=[list(map(int,input().split(" "))) for i in range(h)]
d=[[0]*(w+1) for i in range(h+1)]
for i in range(h):
    for j in range(w):
        if c[i][j]==0:
            d[i+1][j+1]=min(d[i][j],d[i][j+1],d[i+1][j])+1
print(max([max(a) for a in d])**2)