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: Wrong Answer

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] == 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: Wrong Answer

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+1)*(H+1) 

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

if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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] == 1:
                dp[x+1][y+1] = 0
            elif dp[x][y+1] == dp[x][y] and dp[x+1][y] == dp[x][y]:
                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: Wrong Answer

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 = [(-1, -1)]
for i in xrange(h):
    for j in xrange(w):
        v = cnt[i][j]
        while v <= st[-1][0]:
            l, k = st.pop()
            ans = max(ans, min(l, j-k))
        if v:
            st.append((v, j))
    while 0 <= st[-1][0]:
        l, k = st.pop()
        ans = max(ans, min(l, w-k))
print ans**2

Submission status: Wrong Answer

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]
        while v < st[-1][0]:
            l, k = st.pop()
            ans = max(ans, min(l, j-k))
        if st[-1][0] < v:
            st.append((v, j))
    while 0 < st[-1][0]:
        l, k = st.pop()
        ans = max(ans, min(l, w-k))
print ans**2

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def counting(k, v, square):
    square += 1
    for _ in range(square):

        for r in range(k, k + square):
            if r > len(matrix) - 1:
                return False
            for c in range(v, v + square):
                # print(r, c)
                if c > len(matrix[k]) - 1:
                    return False
                if matrix[r][c] == '1':
                    return False
        return True


line = input().split(' ')

answer = [[0 for _ in range(int(line[1]))] for _ in range(int(line[0]))]
matrix = []
maximum = 0

for _ in range(int(line[0])):
    row = input().split(' ')
    matrix.append(row)

    for i in range(len(matrix)):
        for j in range(len(matrix[i])):
            # for m in range(min(int(line[0]), int(line[1]))):
            res = counting(i, j, maximum)
            print(i, j, res)
            if res:
                maximum += 1
            else:
                break

print(maximum * maximum)

Submission status: Wrong Answer

Solution code:
def counting(k, v, square):
    square += 1
    for _ in range(square):

        for r in range(k, k + square):
            if r > len(matrix) - 1:
                return False
            for c in range(v, v + square):
                if c > len(matrix[k]) - 1:
                    return False
                if matrix[r][c] == '1':
                    return False
        return True


line = input().split(' ')

answer = [[0 for _ in range(int(line[1]))] for _ in range(int(line[0]))]
matrix = []
maximum = 0

for _ in range(int(line[0])):
    row = input().split(' ')
    matrix.append(row)

    for i in range(len(matrix)):
        for j in range(len(matrix[i])):
            # for m in range(min(int(line[0]), int(line[1]))):
            res = counting(i, j, maximum)
            if res:
                maximum += 1
            else:
                break

print(maximum * maximum)

Submission status: Wrong Answer

Solution code:
def counting(k, v, square):
    square += 1
    for _ in range(square):

        for r in range(k, k + square):
            if r > len(matrix) - 1:
                return False
            for c in range(v, v + square):
                if c > len(matrix[k]) - 1:
                    return False
                if matrix[r][c] == '1':
                    return False
        return True


line = input().split(' ')

answer = [[0 for _ in range(int(line[1]))] for _ in range(int(line[0]))]
matrix = []
maximum = 0

for _ in range(int(line[0])):
    row = input().split(' ')
    matrix.append(row)

    for i in range(len(matrix)):
        for j in range(len(matrix[i])):
            # for m in range(min(int(line[0]), int(line[1]))):
            res = counting(i, j, maximum)
            if res:
                maximum += 1
            else:
                break

print(1 if maximum == 0 else maximum * maximum)

Submission status: Wrong Answer

Solution code:
def counting(k, v, square):
    square += 1
    for _ in range(square):

        for r in range(k, k + square):
            if r > len(matrix) - 1:
                return False
            for c in range(v, v + square):
                if c > len(matrix[k]) - 1:
                    return False
                if matrix[r][c] == '1':
                    return False
        return True


line = input().split(' ')

answer = [[0 for _ in range(int(line[1]))] for _ in range(int(line[0]))]
matrix = []
maximum = 0
is_over = False
ggg = 0
for _ in range(int(line[0])):
    row = input().split(' ')
    matrix.append(row)

for i in range(len(matrix)):
    for j in range(len(matrix[i])):
        ggg += 1
        for m in range(min(int(line[0]), int(line[1]))):
            res = counting(i, j, maximum)
            if res:
                maximum += 1
            else:
                break

print(1 if maximum == 0 else maximum * maximum)

Submission status: Wrong Answer

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 ** max_square)

Submission status: Wrong Answer

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):
    #         print(m, n, carpet_info[m][n])
    #         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 max_width


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: Wrong Answer

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):
    #         print(m, n, carpet_info[m][n])
    #         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: Wrong Answer

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: Wrong Answer

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

    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

    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: Wrong Answer

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

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

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

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

for i in buf:
    print(i)

print(maxsquare**2)

Submission status: Wrong Answer

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

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

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

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

print(maxsquare**2)

Submission status: Wrong Answer

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

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

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

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

for i in buf:
    print(i)

print(maxsquare**2)

Submission status: Wrong Answer

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

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

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

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


print(maxsquare**2)

Submission status: Wrong Answer

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

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

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

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


print(maxsquare**2)

Submission status: Wrong Answer

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:
            if tile[i-2][j-1]==1 or tile[i-1][j-2]==1 or tile[i-2][j-2]==1:
                buf[i][j] = 1
            elif tile[i-2][j-1]==tile[i-1][j-2]:
                buf[i][j] = buf[i-1][j-1]+1
            else:
                buf[i][j] = min(buf[i-1][j] , buf[i][j-1])+1

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


print(maxsquare**2)

Submission status: Wrong Answer

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(' ')]
    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: Wrong Answer

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):
        self.max_width = self.dp[0][0]
        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: Wrong Answer

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):
        self.max_width = max(self.dp[0])
        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: Wrong Answer

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(H), range(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: Wrong Answer

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

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):
        dp[(h, w)] = min(dp[(h-1, w-1)], dp[(h-1, w)], dp[(h, w-1)]) + 1

print(dp[(H, W)])

Submission status: Wrong Answer

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)

Submission status: Wrong Answer

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)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

ans = 0
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: Wrong Answer

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
for j in range(W): dp[0][j] = (tiles[0][j] + 1)%2
for i in range(H):
    for j in range(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: Wrong Answer

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(lst)
mp.append([-1] * w)

ans = 0
for x in range(w - 1, -1, -1):
  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, (score - last_score)) ** 2)
        
        score_stack.append(score)
        ind_stack.append(last_ind)
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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)]
dp[0][0] = 1 if c[0][0] == 0 else 0
for j in range(W):
    if c[0][0] == 1:
        dp[0][j] = 0
    else:
        dp[0][j] = 1

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

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

print(dp[H-1][W-1])

Submission status: Wrong Answer

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)]
dp[0][0] = 1 if c[0][0] == 0 else 0
for j in range(W):
    if c[0][0] == 1:
        dp[0][j] = 0
    else:
        dp[0][j] = 1

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

maxwidth = 0
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-1][j], dp[i-1][j-1], dp[i][j-1]) + 1
            maxwidth = max(maxwidth,dp[i][j])

print(maxwidth**2)

Submission status: Wrong Answer

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

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: Wrong Answer

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):
        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: Time Limit Exceeded

Solution code:
def counting(k, v, square):
    square += 1
    for _ in range(square):
        for r in range(k, k + square):
            if r > len(matrix) - 1:
                return False
            for c in range(v, v + square):
                if c > len(matrix[k]) - 1:
                    return False
                if matrix[r][c] == '1':
                    return False
        return True


line = input().split(' ')

answer = [[0 for _ in range(int(line[1]))] for _ in range(int(line[0]))]
matrix = []
maximum = 0

for _ in range(int(line[0])):
    row = input().split(' ')
    matrix.append(row)

    for i in range(len(matrix)):
            for j in range(len(matrix[i])):
                for m in range(min(int(line[0]), int(line[1]))):
                    res = counting(i, j, maximum)
                    # print(res)
                    if res:
                        maximum += 1
                    else:
                        break

print(maximum * maximum)

Submission status: Time Limit Exceeded

Solution code:
def counting(k, v, square):
    square += 1
    for _ in range(square):

        for r in range(k, k + square):
            if r > len(matrix) - 1:
                return False
            for c in range(v, v + square):
                if c > len(matrix[k]) - 1:
                    return False
                if matrix[r][c] == '1':
                    return False
        return True


line = input().split(' ')

answer = [[0 for _ in range(int(line[1]))] for _ in range(int(line[0]))]
matrix = []
maximum = 0
is_over = False
ggg = 0
for _ in range(int(line[0])):
    row = input().split(' ')
    matrix.append(row)

for i in range(len(matrix)):
    for j in range(len(matrix[i])):
        ggg += 1
        for m in range(min(int(line[0]), int(line[1]))):
            res = counting(i, j, maximum)
            if res:
                maximum += 1
            else:
                break

print(maximum * maximum)

Submission status: Time Limit Exceeded

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

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