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):
from sys import stdin
readline = stdin.readline

h, w = map(int, readline().split())

dp = [list(map(int, readline().split())) for _ in range(h)]

for i in range(h):
    for j in range(w):
        dp[i][j] ^= 1

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

print(max(y for x in dp for y in x) ** 2)

Solution (Python):



h,w = map(int,input().split())

c = [list(map(int,input().split())) for j in range(h)]
dp = [[0 for i in range(w)] for j in range(h)]

for j in range(h):
    for i in range(w):
        dp[j][i] = c[j][i]


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

for j in range(1,h):
    for i in range(1,w):
        if dp[j][i]:
            dp[j][i] = 1 + min(dp[j-1][i-1], dp[j-1][i], dp[j][i-1])
print(max(y for x in dp for y in x)**2)

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

    dp = [[0] * W for _ in range(H)]

    for x in range(H):
        dp[x][0] = 1 if c[x][0] == 0 else 0
    for y in range(W):
        dp[0][y] = 1 if c[0][y] == 0 else 0

    for x in range(H-1):
        for y in range(W-1):
            if c[x+1][y+1] == 0:
                dp[x+1][y+1] = min([dp[x][y], dp[x][y+1], dp[x+1][y]]) + 1

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


if __name__ == '__main__':
    solve()

Solution (Python):
h, w = map(int, raw_input().split())
c = [map(int, raw_input().split()) for i in xrange(h)]
cnt = [[0]*w for i in xrange(h)]

for j in xrange(w):
    seq = 0
    for i in xrange(h):
        if c[i][j] == 0:
            seq += 1
        else:
            seq = 0
        cnt[i][j] = seq
ans = 0
st = [(0, -1)]
for i in xrange(h):
    for j in xrange(w):
        v = cnt[i][j]
        last = j
        while v < st[-1][0]:
            l, k = st.pop()
            last = k
            ans = max(ans, min(l, j-k))
        if st[-1][0] < v:
            st.append((v, last))
    while 0 < st[-1][0]:
        l, k = st.pop()
        ans = max(ans, min(l, w-k))
print ans**2

Solution (Python):
h,w=map(int,raw_input().split())
c=[[1]*(w+1)]+[[1]+map(int,raw_input().split()) for _ in xrange(h)]
dp=[[0]*(w+1) for i in xrange(h+1)]
for i in xrange(h):
	for j in xrange(w):
		if c[i+1][j+1]==0:
			dp[i+1][j+1]=min(dp[i][j+1],dp[i+1][j],dp[i][j])+1
print(max([max(i) for i in dp])**2)

Solution (Python):
def solve2():
    r, c = map(int, input().split(' '))

    ans_matrix = [[0 for _ in range(c + 1)] for _ in range(r + 1)]
    input_matrix = []

    for _ in range(r):
        input_matrix.append(list(map(int, input().split(' '))))

    largest_square = 0

    for i in range(len(input_matrix)):
        for j in range(len(input_matrix[i])):
            new_i, new_j = i + 1, j + 1
            if input_matrix[i][j] == 0:
                ans_matrix[new_i][new_j] = min(ans_matrix[new_i - 1][new_j], ans_matrix[new_i][new_j - 1], ans_matrix[new_i - 1][new_j - 1]) + 1
                largest_square = ans_matrix[new_i][new_j] if ans_matrix[new_i][new_j] > largest_square else largest_square
            else:
                ans_matrix[new_i][new_j] = 0

    print(largest_square ** 2)


def main():
    solve2()


if __name__ == '__main__':
    main()

Solution (Python):
h, w = map(int, input().split())
floor = [[1] + list(map(int, input().split())) for i in range(h)]
max_square, prev = 0, [0] * (w + 1)
for i in range(h):
    current = [0] * (w + 1)
    for j in range(1, w + 1):
        if floor[i][j]:
            current[j] = 0
            continue
        current[j] = min(prev[j - 1], prev[j], current[j - 1]) + 1
    prev = current
    max_square = max(max_square, max(current))

print(max_square ** 2)

Solution (Python):



"""
input:
4 5
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0
0 0 0 1 0

output:
4
"""
import sys


def solve():
    dp = [[0] * W for _ in range(H)]
    max_width = 0
    for m in range(H):
        for n in range(W):
            dp[m][n] = (int(carpet_info[m][n]) + 1) % 2
            max_width |= dp[m][n]

    for i in range(1, H):
        for j in range(1, W):
            if not int(carpet_info[i][j]):
                dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
                max_width = max(max_width, dp[i][j])
                
    return pow(max_width, 2)


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    H, W = map(int, _input[0].split())
    carpet_info = list(map(lambda x: x.split(), _input[1:]))
    print(solve())

Solution (Python):



"""
input:
4 5
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0
0 0 0 1 0

output:
4
"""
import sys


def solve():
    dp = [[0] * W for _ in range(H)]
    max_width = 0
    for m in range(H):
        for n in range(W):
            dp[m][n] = (int(carpet_info[m][n]) + 1) % 2
            max_width |= dp[m][n]

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

    return pow(max_width, 2)


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    H, W = map(int, _input[0].split())
    carpet_info = list(map(lambda x: x.split(), _input[1:]))
    print(solve())

Solution (Python):



"""
input:
4 5
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0
0 0 0 1 0

output:
4
"""
import sys


def solve():
    dp = [[0] * (W + 1) for _ in range(H + 1)]

    for i in range(H):
        for j in range(W):
            if not int(carpet_info[i][j]):
                dp[i + 1][j + 1] = min(dp[i][j], dp[i][j + 1], dp[i + 1][j]) + 1

    cand = (max(each) for each in dp)
    return pow(max(cand), 2)


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    H, W = map(int, _input[0].split())
    carpet_info = list(map(lambda x: x.split(), _input[1:]))
    print(solve())

Solution (Python):



"""
input:
4 5
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0
0 0 0 1 0

output:
4
"""
import sys


def solve():
    dp = [[0] * (W + 1) for _ in range(H + 1)]

    for i in range(H):
        for j in range(W):
            if not int(carpet_info[i][j]):
                dp[i + 1][j + 1] = min(dp[i][j], dp[i][j + 1], dp[i + 1][j]) + 1

    max_width = max(map(max, dp))
    return pow(max_width, 2)


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    H, W = map(int, _input[0].split())
    carpet_info = list(map(lambda x: x.split(), _input[1:]))
    print(solve())

Solution (Python):
import sys

def solve():
    file_input = sys.stdin
    H, W = map(int, file_input.readline().split())
    dp = [[0] * (W + 1)]
    for line in file_input:
        dp.append([0] + list(map(int, line.split())))
    max_width = 0
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            if dp[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
                max_width = max(max_width, dp[i][j])
    print(max_width ** 2)

solve()

Solution (Python):
import sys

def solve():
    file_input = sys.stdin
    H, W = map(int, file_input.readline().split())
    side_length = 0
    prev = [0] * (W + 1)
    for line in file_input:
        tile_line = map(int, line.split())
        current = [0] * (W + 1)
        for i, tpl in enumerate(zip(tile_line, prev, prev[1:]), start=1):
            t, p1, p2 = tpl
            if t:
                current[i] = 0
            else:
                current[i] = min(p1, p2, current[i - 1]) + 1
        prev = current
        side_length = max(side_length, max(current))
    print(side_length ** 2)

solve()

Solution (Python):
import sys
H,W = map(int, input().split())
C = [list(map(int,i.split())) for i in sys.stdin.readlines()]
G =[[None for i in range(W)] for j in range(H)]

for i in range(W):
  if C[0][i] == 0:
      G[0][i] = 1
  else: G[0][i] = 0
for i in range(H):
  if C[i][0] == 0:
      G[i][0] = 1
  else: G[i][0] = 0


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

ans = max(max(i) for i in G) ** 2
print(str(ans))

Solution (Python):
H,W = map(int,input().split())
tile = [[0 for i in range(W)] for i in range(H)]
buf = [[0 for i in range(W+1)] for i in range(H+1)]
maxsquare = 0

for i in range(H):
    tile[i] = list(map(int,input().split()))

for i in range(1,H+1):
    for j in range(1,W+1):
        if tile[i-1][j-1]!=1:
            buf[i][j] = min(buf[i-1][j],buf[i][j-1],buf[i-1][j-1]) + 1

            if buf[i][j] > maxsquare:
                maxsquare = buf[i][j]

print(maxsquare**2)

Solution (Python):
import sys
h, w = map(int, sys.stdin.readline().split())
dp = [[0 for j in range(w)] for i in range(h)]
G = [[int(j) for j in sys.stdin.readline().split()] for i in range(h)]
maxWidth = 0
for i in range(0, h):
    for j in range(0, 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] == 0):
            dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
            if maxWidth < dp[i][j]:
                maxWidth = dp[i][j]
print(maxWidth * maxWidth)

Solution (Python):
import sys
h, w = map(int, sys.stdin.readline().split())
dp = [[0] * w for _ in range(h)]
G = [[int(j) for j in sys.stdin.readline().split()] for _ in range(h)]
for i in range(0, h):
    for j in range(0, w):
        dp[i][j] = (G[i][j] + 1) % 2
for i in range(1, h):
    for j in range(1, w):
        if(G[i][j] == 0):
            dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
print(max([max(item) for item in dp])**2)

Solution (Python):
import sys
h, w = map(int, sys.stdin.readline().split())
dp = [[0] * w for _ in range(h)]
G = [[int(j) for j in sys.stdin.readline().split()] for _ in range(h)]
for x in range(h):
    dp[x][0] = 1 if G[x][0] == 0 else 0
for y in range(w):
    dp[0][y] = 1 if G[0][y] == 0 else 0
for i in range(1, h):
    for j in range(1, w):
        if(G[i][j] == 0):
            dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
print(max([max(item) for item in dp])**2)

Solution (Python):
import sys
h, w = map(int, sys.stdin.readline().split())
dp = [[0] * w for _ in range(h)]
G = [list(map(int, i.split())) for i in sys.stdin.readlines()]
for x in range(h):
    dp[x][0] = 1 if G[x][0] == 0 else 0
for y in range(w):
    dp[0][y] = 1 if G[0][y] == 0 else 0
for i in range(1, h):
    for j in range(1, w):
        if(G[i][j] == 0):
            dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
print(max(max(i) for i in dp) ** 2)

Solution (Python):
import sys
h, w = map(int, sys.stdin.readline().split())
dp = [[0] * w for _ in range(h)]
G = [[int(j) for j in sys.stdin.readline().split()] for _ in range(h)]
for x in range(h):
    dp[x][0] = 1 if G[x][0] == 0 else 0
for y in range(w):
    dp[0][y] = 1 if G[0][y] == 0 else 0
for i in range(1, h):
    for j in range(1, w):
        if(G[i][j] == 0):
            dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
print(max(max(i) for i in dp) ** 2)

Solution (Python):
import sys
import itertools
h, w = map(int, sys.stdin.readline().split())
dp = [[0] * w for _ in range(h)]
G = [[int(j) for j in sys.stdin.readline().split()] for _ in range(h)]
for x in range(h):
    dp[x][0] = 1 if G[x][0] == 0 else 0
for y in range(w):
    dp[0][y] = 1 if G[0][y] == 0 else 0
for i in range(1, h):
    for j in range(1, w):
        if(G[i][j] == 0):
            dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
print(max(itertools.chain(*dp)) ** 2)

Solution (Python):
import sys
import itertools
h, w = map(int, sys.stdin.readline().split())
dp = [[0] * w for _ in range(h)]
G = [[int(j) for j in sys.stdin.readline().split()] for _ in range(h)]
for x in range(h):
    dp[x][0] = 1 if G[x][0] == 0 else 0
for y in range(w):
    dp[0][y] = 1 if G[0][y] == 0 else 0
for i in range(1, h):
    for j in range(1, w):
        if(G[i][j] == 0):
            dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
print(max(max(i) for i in dp) ** 2)

Solution (Python):
class LargestSquare():
    def __init__(self, map):
        self.max_width = 0
        self.map = []
        self.dp = []
        for r in map:
            self.dp.append([int((x==0)) for x in r])
            self.map.append(r[:])
            if 0 in r:
                self.max_width = 1

    def find(self):
        for row in range(1, len(self.dp)):
            for col in range(1, len(self.dp[0])):
                if self.map[row][col] == 1:
                    self.dp[row][col] = 0
                else:
                    self.dp[row][col] = min(self.dp[row-1][col-1], min(self.dp[row-1][col], self.dp[row][col-1])) + 1
                    self.max_width = max(self.max_width, self.dp[row][col])
        return self.max_width * self.max_width



if __name__ == '__main__':
    
    
    
    height, width = [int(x) for x in input().strip().split(' ')]

    map = []
    for _ in range(height):
        
        map.append([int(x) for x in input().strip().split(' ')])


    
    S = LargestSquare(map)
    result = S.find()

    
    print(result)

Solution (Python):

from itertools import product
H, W = tuple(map(int, input().split()))

C = [tuple(map(int, input().split())) for _ in range(H)]
S = [[1]*W for _ in range(H)]
for h, w in product(range(H), range(W)):
    if C[h][w] == 1:
        S[h][w] = 0

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

result = 0
for sh in S:
    result = max(max(sh), result)

print(result**2)

Solution (Python):
def solve():
    H, W = map(int, input().split())
    c = []
    for _ in range(H):
        c.append(list(map(int, input().split())))
        
    dp = [[0] * W for i in range(H)] 
    
    for i in range(H):
        if c[i][0] == 0: 
            dp[i][0] = 1
    for j in range(W):
        if c[0][j] == 0:
            dp[0][j] = 1
    
    for i in range(H-1):
        for j in range(W-1):
            if c[i+1][j+1] == 0:
                dp[i+1][j+1] = min(dp[i][j], dp[i][j+1], dp[i+1][j]) + 1
                
    
    print(max([max(p) for p in dp]) **2 )
    
if __name__ == '__main__':
    solve()

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

for i in range(H):
    if c[i][0] == 0: 
        dp[i][0] = 1
for j in range(W):
    if c[0][j] == 0:
        dp[0][j] = 1

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

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

Solution (Python):

'''
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_A&lang=jp
???????¨???????
?????§??£?????¢
'''

H, W = map(int, input().split())
C = list()
maxWidth = 0

for h in range(H):
    C.append(list(map(int, input().split())))

dp = dict()
for h in range(H+1):
    dp[(h, 0)] = 0

for w in range(W+1):
    dp[(0, w)] = 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)] = min(dp[(h-1, w-1)], dp[(h-1, w)], dp[(h, w-1)]) + 1
            maxWidth = max(dp[(h, w)], maxWidth)

print(maxWidth**2)

Solution (Python):


from itertools import chain

if __name__ == '__main__':

    H, W = map(int, input().split())
    C = []
    dp = []
    for i in range(H):
        l = input().split()
        C.append([int(x) for x in l])
        dp.append([(int(x) + 1) % 2 for x in l])

    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], dp[i][j - 1],
                               dp[i - 1][j - 1]) + 1
                
    max_width = max(list(chain.from_iterable(dp)))
    print(max_width**2)

Solution (Python):
'''
while True:
    H,W = [int(i) for i in input().split()]

    if H == 0 and W == 0:
        break

    table = [[0 for i in range(W)] for j in range(H)]
    for i in range(H):
        line = input()
        for j in range(W):
            if line[j] == "*":
                table[i][j] = 1
'''

H,W = [int(i) for i in input().split()]
table = [[0 for i in range(W)] for j in range(H)]

ans = 0

for i in range(H):
    table[i] = [1 - int(j) for j in input().split()]

for i in range(H):
    for j in range(W):
        if table[i][j] == 1:
            ans = 1

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

print(ans*ans)

Solution (Python):
H, W = list(map(int, input().split(' ')))
tiles = [list(map(int, input().split(' '))) for i in range(H)]

dp = [[0 for j in range(W)] for i in range(H)]
max_width = 0
for i in range(H):
    dp[i][0] = (tiles[i][0] + 1)%2
    if max_width == 0 and dp[i][0] == 1: max_width = 1
for j in range(W):
    dp[0][j] = (tiles[0][j] + 1)%2
    if max_width == 0 and dp[0][j] == 1: max_width = 1
for i in range(1, H):
    for j in range(1, W):
        if tiles[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
            max_width = max(max_width, dp[i][j])
print(max_width**2)

Solution (Python):
h, w = map(int, input().split())
mp = []
for _ in range(h):
  lst = list(map(int, input().split()))
  cum = []
  acc = 0
  for i in lst:
    if i == 0:
      acc += 1
    else:
      acc = 0
    cum.append(acc)
  mp.append(cum)
mp.append([-1] * w)

ans = 0
for x in range(w):
  score_stack = []
  ind_stack = []
  for y in range(h + 1):

    score = mp[y][x]
    if score_stack == []:
      score_stack.append(score)
      ind_stack.append(y)
    else:
      last_score = score_stack[-1]
      if last_score < score:
        score_stack.append(score)
        ind_stack.append(y)

      elif last_score == score:
        continue

      else:
        while score_stack != [] and score_stack[-1] >= score:
          last_score = score_stack.pop()
          last_ind = ind_stack.pop()

          ans = max(ans, min(y - last_ind, last_score) ** 2)
        
        score_stack.append(score)
        ind_stack.append(last_ind)
print(ans)

Solution (Python):
H, W = map(int, input().split())
c = []
for i in range(H):
    c.append([int(i) for i in input().split()])
dp = [[0 for i in range(W)] for i in range(H)]
maxwidth = 0
for i in range(H):
    for j in range(W):
        dp[i][j] = (c[i][j] + 1) % 2
        maxwidth |= dp[i][j]

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

print(maxwidth**2)

Solution (Python):
H, W = map(int, input().split())
c = []

for i in range(H):
    c.append([int(i) for i in input().split()])
dp = [[0 for i in range(W)] for i in range(H)]

maxwidth = 0

for i in range(H):
    for j in range(W):
        dp[i][j] = (c[i][j] + 1) % 2
        maxwidth |= dp[i][j]

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

print(maxwidth**2)

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

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

max_edge = 0

for i in range(h):
    if c[i][0] == 0:
        dp[i][0] = 1
        max_edge = 1
for i in range(w):
    if c[0][i] == 0:
        dp[0][i] = 1
        max_edge = 1
        
        
for i in range(1,h):
    for j in range(1,w):
        if c[i][j] == 1:
            dp[i][j] = 0
        else:
            dp[i][j] = min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1]) + 1
            max_edge = max(max_edge,dp[i][j])

print(max_edge**2)

Solution (Python):
import sys

import math
import collections

import bisect
import itertools
import fractions

import copy

import decimal

import queue



sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7


ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))



eps = 10 ** (-9)


def main():
    h, w = ns()
    mat = [na() for _ in range(h)]

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

    ans = 0
    for i in range(h):
        for j in range(w):
            if mat[i][j]:
                continue
            if mat[i][j] == 0:
                dp[i][j] = 1
            if i > 0 and j > 0:
                dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
            ans = max(ans, dp[i][j])

    print(ans ** 2)


if __name__ == '__main__':
    main()

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    H, W = LI()
    c = [LI() for _ in range(H)]

    
    dp = [[0] * (W + 1) for _ in range(H + 1)]

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

    print(max_len ** 2)

    
    

if __name__ == '__main__':
    resolve()

Solution (Python):
H,W = map(int,input().split())
M = [[0]*(W+1) for _ in range(H+1)]
for i in range(H):
    M[i+1][1:] = list(map(int,input().split()))

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

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

Solution (Python):
H, W = map(int, input().split())
T = [[int(t) for t in input().split()] for _ in range(H)]
A = [[0] * W for _ in range(H)]

for i in range(H):
    for j in range(W):
        if T[i][j] == 1:
            A[i][j] = 0
        elif i == 0 or j == 0:
            A[i][j] = 1
        else:
            A[i][j] = min(A[i - 1][j], A[i][j - 1], A[i - 1][j - 1]) + 1

mx = 0
for a in A:
    mx = max(mx, max(a))

print(mx ** 2)

Solution (Python):


import sys
H, W = map(int, sys.stdin.readline().strip().split())
dp = [[0] * (W + 1) for _ in range(H + 1)]

for h in range(1, H + 1):
    c = list(map(int, sys.stdin.readline().strip().split()))
    dirty = [i for i, x in enumerate(c) if x == 1]
    for w in dirty:
        dp[h][w + 1] = 'dirty'

ans = 0
for h in range(1, H + 1):
    for w in range(1, W + 1):
        if dp[h][w] == 'dirty':
            dp[h][w] =0
            continue
        dp[h][w] = min(dp[h][w - 1], dp[h - 1][w - 1], dp[h - 1][w]) + 1
        ans = max(dp[h][w], ans)

print(ans ** 2)

Solution (Python):
H,W = map(int, raw_input().split())
C = [map(int, raw_input().split()) for _ in range(H)]

DP = [[0]*(W+1) for _ in range(H+1)]

for i in range(1, H+1):
    for j in range(1, W+1):
        if C[i-1][j-1] != 1:
            DP[i][j] = min(
                DP[i-1][j-1],
                DP[i-1][j],
                DP[i][j-1]) + 1

ans = max([max(dp) for dp in DP]) ** 2
print ans

Solution (Python):

"""
Writer: SPD_9X2
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_3_A&lang=ja
dpだろうなぁ

dp[i][j] = min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j]) = そこを右下にしてできる最大の正方形
っぽい？
"""

H,W = map(int,input().split())

c = []

for i in range(H):
    C = list(map(int,input().split()))
    c.append(C)

dp = [ [float("inf")] * W for i in range(H) ]
ans = 0

for i in range(H):

    for j in range(W):

        if c[i][j] == 1:
            dp[i][j] = 0
            continue

        if i == 0 or j == 0:
            dp[i][j] = 1
        else:
            dp[i][j] = min(dp[i-1][j-1],dp[i][j-1],dp[i-1][j]) + 1

        ans = max(ans , dp[i][j]**2)

print (ans)

Solution (Python):
import sys,bisect
sys.setrecursionlimit(15000)
h,w = map(int,sys.stdin.readline().split())
dp = [[0]*w for _ in range(h)]
m = 0
for i in range(h):
  a = list(map(int,sys.stdin.readline().split()))
  for j in range(w):
    if a[j] == 1:
      dp[i][j] = 0
    elif i == 0 or j == 0:
      dp[i][j] = 1
      m = max(m,dp[i][j])
    else:
      dp[i][j] = min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])+1
      m = max(m,dp[i][j])
print(m*m)

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

ans=0
DP=[[0]*(w+2) for _ in range(h+2)]
for i in range(1,h+1):
    for j in range(1,w+1):
        if HW[i-1][j-1]==1:DP[i][j]=0
        else:
            DP[i][j]=min(DP[i-1][j-1],DP[i-1][j],DP[i][j-1])+1
            ans=max(ans,DP[i][j])

print(ans**2)

Solution (Python):


iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, W = iim()

    dp = [0] * W
    dp0 = [0] * W
    ans = 0
    for i in range(H):
        C = list(iim())

        dp[0] = C[0] ^ 1
        for i in range(1, W):
            ci = C[i]
            if ci:
                dp[i] = 0
            else:
                dp[i] = min(dp0[i-1], dp[i-1], dp0[i]) + 1
        

        ans = max(ans, *dp)
        dp, dp0 = dp0, dp

    print(ans**2)




if __name__ == "__main__":
    resolve()

Solution (Python):
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30

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

if __name__ == '__main__':
    main()

Solution (Python):
hw = list(map(int, input().split()))
h = hw[0]
w = hw[1]

tile = []
for i in range(h):
    tile.append(list(map(int, input().split())))

c = [[0] * w for i in range(h)]

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

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

r = 0
for j in range(1, w):
    for i in range(1, h):
        if tile[i][j] == 0:
            c[i][j] = min([c[i-1][j-1], c[i][j-1], c[i-1][j]]) + 1
        else:
            c[i][j] = 0

for j in range(w):
    for i in range(h):
        if r < c[i][j]:
            r = c[i][j]

print(r**2)

Solution (Python):


maxval = 0

nums=list(map(int,input().split()))
h = nums[0]
w = nums[1]
G = [[0 for i in range(w)] for j in range(h)]
dp = [[0 for i in range(w)] for j in range(h)]
for i in range(h):
    nums=list(map(int,input().split()))
    for j in range(w):
        G[i][j] = nums[j]

for i in range(h):
    for j in range(w):
        if G[i][j] == 1:
            dp[i][j] = 0
        else:
            if i == 0 or j == 0:
                dp[i][j] = 1
                if maxval == 0:
                    maxval = 1
            else:
                dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
                if dp[i][j] > maxval:
                    maxval = dp[i][j]
                    

print(maxval ** 2)

Solution (Python):



from itertools import product, chain


H, W = list(map(int, input().split()))
C = []
for i in range(H):
    C.append(list(map(int, input().split())))




dp = [[-1] * W for _ in range(H)]  



for j in range(W):
    if C[0][j] == 1:
        dp[0][j] = 0
    else:
        dp[0][j] = 1

for i in range(H):
    if C[i][0] == 1:
        dp[i][0] = 0
    else:
        dp[i][0] = 1



for i, j in product(range(1, H), range(1, W)):
    if C[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

side_length = max(chain.from_iterable(dp))  
print(side_length**2)

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

def Largest_Square(grid):
    h=len(grid);w=len(grid[0])
    dp=[[0]*w for i in range(h)]
    maxlenth=0
    for i in range(h):
        for j in range(w):
            dp[i][j]=(grid[i][j]+1)%2
            maxlenth=max(maxlenth,dp[i][j])
    for i in range(1,h):
        for j in range(1,w):
            if grid[i][j]:
                continue
            else:
                dp[i][j]=min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])+1
                maxlenth=max(maxlenth,dp[i][j])
    return maxlenth**2
print(Largest_Square(grid))

Solution (Python):
h, w = map(int, input().split())

dp = [0] * w
max_d = 0
for _ in range(h):
    dp_prev = dp[:]
    tiles = list(map(int, input().split()))
    dp[0] = 0 if tiles[0] else 1
    for i in range(1, w):
        dp[i] = 0 if tiles[i] else min(dp[i-1], dp_prev[i], dp_prev[i-1]) + 1
    max_d = max(max_d, max(dp))

print(max_d**2)

Solution (Python):
H,W = [int(_) for _ in input().split()]
HW = [[0]*W for _ in range(H)]
for i in range(H):
    c = 0
    for j in [int(_) for _ in input().split()]:
        if j == 1:
            HW[i][c] = 1
        c += 1
dp = [[0]*W for _ in range(H)]
for j in range(W):
    if HW[0][j] == 0:
        dp[0][j] = 1
    else:
        dp[0][j] = 0
for i in range(H):
    if HW[i][0] == 0:
        dp[i][0] = 1
    else:
        dp[i][0] = 0
for i in range(1, H):
    for j in range(1, W):
        if HW[i][j] == 1:
            dp[i][j] = 0
        else:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1]) + 1
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans,dp[i][j])
print(ans*ans)

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

dp = [[0 for i in range(W)] for j in range(H)]
max_width = 0
for i in range(H):
  for j in range(W):
    if square[i][j] == 1:
      continue
    if i-1 < 0 and j-1 < 0:
      dp[i][j] = 1
    elif i-1 < 0 or j-1 < 0:
      dp[i][j] = 1
    else:
      dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1

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

print(max_width**2)

Solution (Python):
t,*L=open(0)
H,W=map(int,t.split())
bef=[0]*(W+1)
a=0
for l in L:
	cur=[0]*(W+1)
	for i in range(W):
		if l[i*2]=="0":
			cur[i+1]=min(cur[i],bef[i],bef[i+1])+1
	a=max(a,max(cur))
	bef=cur
print(a**2)

Solution (Python):

h, w = map(int, input().split( ))



c=[[0 for _ in range(w)]]
DP = [[0 for _ in range(w)] for __ in range(h+1)]
for _ in range(h):
    c_tmp = list(map(int, input().split( )))
    c.append( c_tmp )


for i in range(w):
    for j in range(1,h+1):
        if c[j][i] == 1:
            DP[j][i] = 0
        else:
            DP[j][i] = min(DP[j-1][i],DP[j][i-1],DP[j-1][i-1])+1
 
mx =0

for i in range(h+1):
    mx =max(mx,max(DP[i]))
print(mx**2)