Problem:


Largest Square

  Given a matrix (H &times; W) which contains only 1 and 0, find the area of the largest square matrix which only contains 0s.

Input

H W
c1,1 c1,2 ... c1,W
c2,1 c2,2 ... c2,W
:
cH,1 cH,2 ... cH,W

  In the first line, two integers H and W separated by a space character are given. In the following H lines, ci,j, elements of the H &times; 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



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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

h,w = map(int,input().split())
#1 -> ?±????????????????, 0 -> ?¶????????????????
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]

#0 -> ?±????????????????, 1 -> ?¶????????????????
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
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())

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
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())

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
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())

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""
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())

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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__':
    # ??????????????\???
    # f = open('input.txt')
    #height, width = [int(x) for x in f.readline().strip().split(' ')]
    height, width = [int(x) for x in input().strip().split(' ')]

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


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

    # ???????????¨???
    print(result)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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)

Submission status: Accepted

Solution code:
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(dp)
    print(max([max(p) for p in dp]) **2 )
    
if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
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(dp)
print(max([max(p) for p in dp]) **2 )

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
'''
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)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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)

Submission status: Accepted

Solution code:
'''
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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):
#    print(score_stack, ind_stack)
    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()
#          print(last_score, last_ind, ans)
          ans = max(ans, min(y - last_ind, last_score) ** 2)
        
        score_stack.append(score)
        ind_stack.append(last_ind)
print(ans)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

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

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

# ===CODE===

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()

Submission status: Accepted

Solution code:
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[i][j]: (i-1, j-1)から左上に作れる最大正方形の1辺の長さ
    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)

    # for i in dp:
    #     print(i)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# DPL_3_A: Largest Square

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)

Submission status: Accepted

Solution code:
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

Submission status: Accepted

Solution code:

"""
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
#!python3

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
        #print(*dp)

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

    print(ans**2)




if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
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)
    # for i in dp:
    #     print(i)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:


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)

Submission status: Accepted

Solution code:
# https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/all/DPL_3_A
# P426の解説がわかりやすい。なるほどなぁという感じ。

from itertools import product, chain

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

# dp (H,W) ... dp[i][j]においてはC[i][j]から左上に向かってできる最大の正方形の辺の長さを記録していく

# dpテーブルの作成
dp = [[-1] * W for _ in range(H)]  # (H,W)

# dpテーブルの初期化
# 今回は0行目と0列目が即座にわかる
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


# dpテーブルの更新
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))  # flatten
print(side_length**2)

Submission status: Accepted

Solution code:
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))