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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

h, w = map(int, input().split( ))
#c = [ [0] * w ]
#下の奴がまずい。各行が同一のアドレス指してる。上も一応変えておく。
#DP = [ [0] * w ] * ( h + 1 )
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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  # 0 -> 1, 1 -> 0

    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)  # type: ignore

Submission status: Accepted

Solution code:
# DPL 3 A

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

Submission status: Accepted

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

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[i][j] := i,jを右端とする最大正方形の辺の長さ
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:
            # i,jが汚れマスでなければ、左、左上、上から遷移させてくる
            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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Runtime Error

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(H):
        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] == 1:
                dp[x+1][y+1] = 0
            elif c[x][y+1] == 0 and c[x+1][y] == 0:
                dp[x+1][y+1] = dp[x][y] + 1
            else:
                dp[x+1][y+1] = 1

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


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

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

ans = []
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
            ans.append(G[i][j])
        else:G[i][j] = 0

ans = max(ans) ** 2
print(str(ans))

Submission status: Runtime Error

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

ans = []
for i in range(W):
  if C[0][i] == 0:
      G[0][i] = 1
      ans.append(1)
  else: G[0][i] = 0
for i in range(H):
  if C[i][0] == 0:
      G[i][0] = 1
      ans.append(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
            ans.append(G[i][j])
        else:G[i][j] = 0

ans = max(ans) ** 2
print(str(ans))

Submission status: Runtime Error

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(sum(dp, []) ** 2)

Submission status: Runtime Error

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(sum(dp, []) ** 2))

Submission status: Runtime Error

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[:])

    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(' ')]
    map = []
    for _ in range(height):
        map.append([int(x) for x in f.readline().strip().split(' ')])


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

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

Submission status: Runtime Error

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


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

    max_width = 1
    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(max_width, dp[i][j])
    print(max_width**2)
s