Problem:


正方形探索

縦に n 行、横に n 列並べられた、合計  n &times; n のマス目があります。いくつかのマス目には印がついています。各マス目の印の状態を読み込み、印のついていないマス目だけからなる最大の正方形の辺の長さを出力として表示するプログラムを作成してください。

たとえば各データセットで以下のようなデータが与えられます。

10
...*....**
..........
**....**..
........*.
..*.......
..........
.*........
..........
....*..***
.*....*...

入力データの一行が、一行のマス目を表現します。入力データの文字列のうち、.（ピリオド）は印のついていないマス目、*（アスタリスク）は印のついているマス目を示しています。

上記の例では、下図の 0 で示される正方形が最大となります。

...*....**
..........
**....**..
...00000*.
..*00000..
...00000..
.*.00000..
...00000..
....*..***
.*....*...

よって、5 と出力すれば正解になります。

なお、すべてのマス目に印がついている場合には、0 を出力してください。

Input

上記形式で複数のデータセットが与えられます。
n が 0 のとき入力の最後とします。n は 1000 以下とします。入力データの文字列には、ピリオド、アスタリスク、改行以外の文字は含まれません。データセットの数は 50 を超えません。

Output

各データセットに対し、最大の正方形の辺の長さ（整数）を１行に出力して下さい。

Sample Input

10
...*....**
..........
**....**..
........*.
..*.......
..........
.*........
..........
....*..***
.*....*...
10
****.*****
*..*.*....
****.*....
*....*....
*....*****
..........
****.*****
*..*...*..
****...*..
*..*...*..
0

Output for the Sample Input

5
3



Sample input:
10
...*....**
..........
**....**..
........*.
..*.......
..........
.*........
..........
....*..***
.*....*...
10
****.*****
*..*.*....
****.*....
*....*....
*....*****
..........
****.*****
*..*...*..
****...*..
*..*...*..
0


Sample output:
5
3

Submission status: Time Limit Exceeded

Solution code:
while True:
    n=input()
    if n==0:
        break
    dp=[[0 for i in range(n)]for j in range(n)]
    flag0=0
    for i in range(n):
        j=0
        for c in raw_input():
            if c == ".":
                dp[i][j]=1
                flag0=1
            j+=1
    if flag0==0:
        print 0
    else:
        solve=1
        while True:
            flag=0
            for y in xrange(n-solve):
                for x in xrange(n-solve):
                    if dp[y][x]==solve:
                        old=dp[y][x]
                        dp[y][x]=min(dp[y+1][x],dp[y][x+1],dp[y+1][x+1])+1
                        if old !=dp[y][x]:
                            flag=1
            if flag==0:
                break
            solve+=1
        print solve

Submission status: Time Limit Exceeded

Solution code:
while True:
    n=input()
    if n==0:
        break
    dp=[[0 for i in range(n)]for j in range(n)]
    flag0=0
    for i in range(n):
        j=0
        for c in raw_input():
            if c == ".":
                dp[i][j]=1
                flag0=1
            j+=1
    if flag0==0:
        print 0
    else:
        solve=1
        while True:
            flag=0
            for y in xrange(n-solve):
                for x in xrange(n-solve):
                    if dp[y][x]==solve and dp[y+1][x]==solve and\
                       dp[y][x+1]==solve and dp[y+1][x+1]==solve:
                        dp[y][x]=solve+1
                        flag=1
            if flag==0:
                break
            solve+=1
        print solve

Submission status: Time Limit Exceeded

Solution code:
while True:
    n=input()
    if n==0:
        break
    dp=[[0 for i in range(n)]for j in range(n)]
    flag0=0
    for i in range(n):
        j=0
        for c in raw_input():
            if c == ".":
                dp[i][j]=1
                flag0=1
            j+=1
    if flag0==0:
        print 0
    else:
        solve=1
        while True:
            flag=0
            for y in xrange(n-1):
                for x in xrange(n-1):
                    if dp[y][x]==solve and dp[y+1][x]==solve and\
                       dp[y][x+1]==solve and dp[y+1][x+1]==solve:
                        dp[y][x]=solve+1
                        flag=1
            if flag==0:
                break
            solve+=1
        print solve

Submission status: Time Limit Exceeded

Solution code:
while True:
    n=input()
    if n==0:
        break
    dp=[[0 for i in range(n)]for j in range(n)]
    flag0=0
    for i in range(n):
        j=0
        for c in raw_input():
            if c == ".":
                dp[i][j]=1
                flag0=1
            j+=1
    if flag0==0:
        print 0
    else:
        solve=1
        while True:
            flag=0
            for y in xrange(n-1):
                for x in xrange(n-1):
                    if dp[y][x]!=0:
                        old = dp[y][x]
                        dp[y][x]=min(dp[y+1][x],dp[y][x+1],dp[y+1][x+1])+1
                        if old!=dp[y][x]:
                            flag=1
            if flag==0:
                break
            solve+=1
        print solve

Submission status: Time Limit Exceeded

Solution code:
while True:
    n=input()
    if n==0:
        break
    dp=[[0 for i in range(n)]for j in range(n)]
    flag0=0
    for i in range(n):
        j=0
        for c in raw_input():
            if c == ".":
                dp[i][j]=1
                flag0=1
            j+=1
    if flag0==0:
        print 0
    else:
        solve=1
        while True:
            flag=0
            for y in xrange(n-1):
                for x in xrange(n-1):
                    if dp[y][x]!=0:
                        old = dp[y][x]
                        dp[y][x]=min(dp[y+1][x],dp[y][x+1],dp[y+1][x+1])+1
                        if dp[y][x]-old==1:
                            flag=1
            if flag==0:
                break
            solve+=1
        print solve

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0092
"""
import sys



def find_square(data):
    max_size = 0
    lmap = []
    for row in data:
        temp = [0]
        for c in row:
            if c == '.':
                temp.append(1)
            else:
                temp.append(0)
        lmap.append(temp)
        temp = [0]

    for y in range(1, len(lmap)):
        for x in range(1, len(lmap[0])):
            if lmap[y][x] == 1:
                if lmap[y-1][x-1] != 0 and lmap[y-1][x] != 0 and lmap[y][x-1] != 0:
                    lmap[y][x] = min(lmap[y-1][x-1], min(lmap[y-1][x], lmap[y][x-1])) + 1
                    if lmap[y][x] > max_size:
                        max_size = lmap[y][x]
    return max_size


def main(args):
    while True:
        n = int(input())
        if n == 0:
            break
        data = [input() for _ in range(n)]
        result = find_square(data)
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0092
"""
import sys


def find_square0(data):
    # 3.51[s]
    max_size = 0
    dp = [] # dp??¨???2?¬??????????
    # '.'????????????1??????'*'????????????0????????????
    for row in data:
        temp = []
        for c in row:
            if c == '.':
                temp.append(1)
            else:
                temp.append(0)
        dp.append(temp)

    # ????±?????????????????????????????????£????????????????????£?????¢????¢??????§??????????????§????????????
    for y in range(1, len(dp)):
        for x in range(1, len(dp[0])):
            if dp[y][x] == 1:
                dp[y][x] = min(dp[y-1][x-1], dp[y-1][x], dp[y][x-1]) + 1
                if dp[y][x] > max_size:
                    max_size = dp[y][x]
    return max_size


def find_square2(data):
    # 2.80[s]
    max_size = 0
    dp = [[0]*len(data[0]) for _ in range(len(data))] # dp??¨???2?¬???????????????¨??????0??§?????????
    # '.'????????????1???
    for y, row in enumerate(data):
        for x, c in enumerate(row):
            if c == '.':
                dp[y][x] = 1

    # (?????¨???(curr_row)??¨???????????????(prev_row)????????¢????????????????????§?????????????????????)
    prev_row = dp[0]
    for curr_row in dp[1:]:
        for x, t in enumerate(curr_row[1:], start=1):
            if t == 1:
                curr_row[x] = min(prev_row[x-1], prev_row[x], curr_row[x-1]) + 1
                if curr_row[x] > max_size:
                    max_size = curr_row[x]
        prev_row = curr_row
    return max_size


def find_square3(data):
    from array import array
    max_size = 0
    dp = [array('I', [0]*len(data[0])) for _ in range(len(data))]  # ????¬?????????????array??????????????§?¢????
    # '.'????????????1???
    for y, row in enumerate(data):
        for x, c in enumerate(row):
            if c == '.':
                dp[y][x] = 1

    prev_row = dp[0]
    for curr_row in dp[1:]:
        for x, t in enumerate(curr_row[1:], start=1):
            if t == 1:
                curr_row[x] = min(prev_row[x-1], prev_row[x], curr_row[x-1]) + 1
                if curr_row[x] > max_size:
                    max_size = curr_row[x]
        prev_row = curr_row
    return max_size


def find_square4(data):
    # 4.91[s]
    max_size = 0
    dp = [0 for _ in range(1024*1024)]
    # '.'????????????1???
    for y, row in enumerate(data):
        for x, c in enumerate(row):
            if c == '.':
                dp[y*1024+x] = 1

    # ????±?????????????????????????????????£????????????????????£?????¢????¢??????§??????????????§????????????
    for y in range(1, len(data)):
        for x in range(1, len(data)):
            if dp[y*1024+x] == 1:
                dp[y*1024+x] = min(dp[(y-1)*1024+x-1], dp[(y-1)*1024+x], dp[y*1024+x-1]) + 1
                if dp[y*1024+x] > max_size:
                    max_size = dp[y*1024+x]
    return max_size



def find_square5(data):
    # [s]
    from array import array
    max_size = 0
    # dp = [0 for _ in range(1024*1024)]
    dp = array('I', [0]*1024*1024)
    # '.'????????????1???
    for y, row in enumerate(data):
        for x, c in enumerate(row):
            if c == '.':
                dp[y*1024+x] = 1

    # ????±?????????????????????????????????£????????????????????£?????¢????¢??????§??????????????§????????????
    for y in range(1, len(data)):
        for x in range(1, len(data)):
            if dp[y*1024+x] == 1:
                dp[y*1024+x] = min(dp[(y-1)*1024+x-1], dp[(y-1)*1024+x], dp[y*1024+x-1]) + 1
                if dp[y*1024+x] > max_size:
                    max_size = dp[y*1024+x]
    return max_size




def main(args):
    while True:
        n = int(input())
        if n == 0:
            break
        data = [input() for _ in range(n)]
        result = find_square5(data)
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0092
"""
import sys


def find_square0(data):
    # 3.51[s]
    max_size = 0
    dp = [] # dp??¨???2?¬??????????
    # '.'????????????1??????'*'????????????0????????????
    for row in data:
        temp = []
        for c in row:
            if c == '.':
                temp.append(1)
            else:
                temp.append(0)
        dp.append(temp)

    # ????±?????????????????????????????????£????????????????????£?????¢????¢??????§??????????????§????????????
    for y in range(1, len(dp)):
        for x in range(1, len(dp[0])):
            if dp[y][x] == 1:
                dp[y][x] = min(dp[y-1][x-1], dp[y-1][x], dp[y][x-1]) + 1
                if dp[y][x] > max_size:
                    max_size = dp[y][x]
    return max_size


def find_square2(data):
    # 2.80[s]
    max_size = 0
    dp = [[0]*len(data[0]) for _ in range(len(data))] # dp??¨???2?¬???????????????¨??????0??§?????????
    # '.'????????????1???
    for y, row in enumerate(data):
        for x, c in enumerate(row):
            if c == '.':
                dp[y][x] = 1

    # (?????¨???(curr_row)??¨???????????????(prev_row)????????¢????????????????????§?????????????????????)
    prev_row = dp[0]
    for curr_row in dp[1:]:
        for x, t in enumerate(curr_row[1:], start=1):
            if t == 1:
                curr_row[x] = min(prev_row[x-1], prev_row[x], curr_row[x-1]) + 1
                if curr_row[x] > max_size:
                    max_size = curr_row[x]
        prev_row = curr_row
    return max_size


def find_square3(data):
    from array import array
    max_size = 0
    dp = [array('I', [0]*len(data[0])) for _ in range(len(data))]  # ????¬?????????????array??????????????§?¢????
    # '.'????????????1???
    for y, row in enumerate(data):
        for x, c in enumerate(row):
            if c == '.':
                dp[y][x] = 1

    prev_row = dp[0]
    for curr_row in dp[1:]:
        for x, t in enumerate(curr_row[1:], start=1):
            if t == 1:
                curr_row[x] = min(prev_row[x-1], prev_row[x], curr_row[x-1]) + 1
                if curr_row[x] > max_size:
                    max_size = curr_row[x]
        prev_row = curr_row
    return max_size


def find_square4(data):
    # 4.91[s]
    max_size = 0
    dp = [0 for _ in range(1024*1024)]
    # '.'????????????1???
    for y, row in enumerate(data):
        for x, c in enumerate(row):
            if c == '.':
                dp[y*1024+x] = 1

    # ????±?????????????????????????????????£????????????????????£?????¢????¢??????§??????????????§????????????
    for y in range(1, len(data)):
        for x in range(1, len(data)):
            if dp[y*1024+x] == 1:
                dp[y*1024+x] = min(dp[(y-1)*1024+x-1], dp[(y-1)*1024+x], dp[y*1024+x-1]) + 1
                if dp[y*1024+x] > max_size:
                    max_size = dp[y*1024+x]
    return max_size


def find_square4_2(data):
    # [s]
    max_size = 0
    n = len(data)
    dp = [0 for _ in range(n**2)]
    # '.'????????????1???
    for y, row in enumerate(data):
        for x, c in enumerate(row):
            if c == '.':
                dp[y*n+x] = 1

    # ????±?????????????????????????????????£????????????????????£?????¢????¢??????§??????????????§????????????
    for y in range(1, len(data)):
        for x in range(1, len(data)):
            if dp[y*n+x] == 1:
                dp[y*n+x] = min(dp[(y-1)*n+x-1], dp[(y-1)*n+x], dp[y*n+x-1]) + 1
                if dp[y*n+x] > max_size:
                    max_size = dp[y*n+x]
    return max_size



def find_square5(data):
    # 5.09[s]
    from array import array
    max_size = 0
    # dp = [0 for _ in range(1024*1024)]
    dp = array('I', [0]*1024*1024)
    # '.'????????????1???
    for y, row in enumerate(data):
        for x, c in enumerate(row):
            if c == '.':
                dp[y*1024+x] = 1

    # ????±?????????????????????????????????£????????????????????£?????¢????¢??????§??????????????§????????????
    for y in range(1, len(data)):
        for x in range(1, len(data)):
            if dp[y*1024+x] == 1:
                dp[y*1024+x] = min(dp[(y-1)*1024+x-1], dp[(y-1)*1024+x], dp[y*1024+x-1]) + 1
                if dp[y*1024+x] > max_size:
                    max_size = dp[y*1024+x]
    return max_size




def main(args):
    while True:
        n = int(input())
        if n == 0:
            break
        data = [input() for _ in range(n)]
        result = find_square4_2(data)
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0092
"""
import sys


def find_square0(data):
    # 3.51[s]
    max_size = 0
    dp = [] # dp??¨???2?¬??????????
    # '.'????????????1??????'*'????????????0????????????
    for row in data:
        temp = []
        for c in row:
            if c == '.':
                temp.append(1)
            else:
                temp.append(0)
        dp.append(temp)

    # ????±?????????????????????????????????£????????????????????£?????¢????¢??????§??????????????§????????????
    for y in range(1, len(dp)):
        for x in range(1, len(dp[0])):
            if dp[y][x] == 1:
                dp[y][x] = min(dp[y-1][x-1], dp[y-1][x], dp[y][x-1]) + 1
                if dp[y][x] > max_size:
                    max_size = dp[y][x]
    return max_size


def find_square2(data):
    # 2.80[s]
    max_size = 0
    dp = [[0]*len(data[0]) for _ in range(len(data))] # dp??¨???2?¬???????????????¨??????0??§?????????
    # '.'????????????1???
    for y, row in enumerate(data):
        for x, c in enumerate(row):
            if c == '.':
                dp[y][x] = 1

    # (?????¨???(curr_row)??¨???????????????(prev_row)????????¢????????????????????§?????????????????????)
    prev_row = dp[0]
    for curr_row in dp[1:]:
        for x, t in enumerate(curr_row[1:], start=1):
            if t == 1:
                curr_row[x] = min(prev_row[x-1], prev_row[x], curr_row[x-1]) + 1
                if curr_row[x] > max_size:
                    max_size = curr_row[x]
        prev_row = curr_row
    return max_size


def find_square3(data):
    from array import array
    max_size = 0
    dp = [array('I', [0]*len(data[0])) for _ in range(len(data))]  # ????¬?????????????array??????????????§?¢????
    # '.'????????????1???
    for y, row in enumerate(data):
        for x, c in enumerate(row):
            if c == '.':
                dp[y][x] = 1

    prev_row = dp[0]
    for curr_row in dp[1:]:
        for x, t in enumerate(curr_row[1:], start=1):
            if t == 1:
                curr_row[x] = min(prev_row[x-1], prev_row[x], curr_row[x-1]) + 1
                if curr_row[x] > max_size:
                    max_size = curr_row[x]
        prev_row = curr_row
    return max_size


def find_square4(data):
    # ???????????????
    # 4.91[s]
    max_size = 0
    dp = [0 for _ in range(1024*1024)]
    # '.'????????????1???
    for y, row in enumerate(data):
        for x, c in enumerate(row):
            if c == '.':
                dp[y*1024+x] = 1

    # ????±?????????????????????????????????£????????????????????£?????¢????¢??????§??????????????§????????????
    for y in range(1, len(data)):
        for x in range(1, len(data)):
            if dp[y*1024+x] == 1:
                dp[y*1024+x] = min(dp[(y-1)*1024+x-1], dp[(y-1)*1024+x], dp[y*1024+x-1]) + 1
                if dp[y*1024+x] > max_size:
                    max_size = dp[y*1024+x]
    return max_size


def find_square4_2(data):
    # ???????????????
    # 5.24[s]
    max_size = 0
    n = len(data)
    dp = [0 for _ in range(n**2)]
    # '.'????????????1???
    for y, row in enumerate(data):
        for x, c in enumerate(row):
            if c == '.':
                dp[y*n+x] = 1

    # ????±?????????????????????????????????£????????????????????£?????¢????¢??????§??????????????§????????????
    for y in range(1, len(data)):
        for x in range(1, len(data)):
            if dp[y*n+x] == 1:
                dp[y*n+x] = min(dp[(y-1)*n+x-1], dp[(y-1)*n+x], dp[y*n+x-1]) + 1
                if dp[y*n+x] > max_size:
                    max_size = dp[y*n+x]
    return max_size



def find_square5(data):
    # 5.09[s]
    from array import array
    max_size = 0
    # dp = [0 for _ in range(1024*1024)]
    dp = array('I', [0 for _ in range(1024*1024)])
    # '.'????????????1???
    for y, row in enumerate(data):
        for x, c in enumerate(row):
            if c == '.':
                dp[y*1024+x] = 1

    # ????±?????????????????????????????????£????????????????????£?????¢????¢??????§??????????????§????????????
    for y in range(1, len(data)):
        for x in range(1, len(data)):
            if dp[y*1024+x] == 1:
                dp[y*1024+x] = min(dp[(y-1)*1024+x-1], dp[(y-1)*1024+x], dp[y*1024+x-1]) + 1
                if dp[y*1024+x] > max_size:
                    max_size = dp[y*1024+x]
    return max_size




def main(args):
    while True:
        n = int(input())
        if n == 0:
            break
        data = [input() for _ in range(n)]
        result = find_square5(data)
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Time Limit Exceeded

Solution code:
# Aizu Problem 0092: Square Searching
#
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


while True:
    n = int(input())
    if n == 0:
        break
    dp = [0] * n**2
    for row in range(n):
        line = input().strip()
        for col in range(n):
            if line[col] == '.':
                dp[row * n + col] = 1
    for row in range(1, n):
        for col in range(1, n):
            if dp[row * n + col] == 1:
                dp[row * n + col] = min(dp[(row - 1) * n + col], \
                                    dp[(row - 1) * n + col - 1], \
                                    dp[row * n + col - 1]) + 1
    print(max(dp))

Submission status: Time Limit Exceeded

Solution code:
# Aizu Problem 0092: Square Searching
#
import sys, math, os

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


while True:
    n = int(input())
    if n == 0:
        break
    dp = [[0 for col in range(n)] for row in range(n)]
    for row in range(n):
        line = input().strip()
        for col in range(n):
            if line[col] == '.':
                dp[row][col] = 1
    for row in range(1, n):
        for col in range(1, n):
            if dp[row][col] == 1:
                dp[row][col] = min(dp[row - 1][col], dp[row - 1][col - 1], \
                                    dp[row][col - 1]) + 1
    print(max([max(row) for row in dp]))

Submission status: Time Limit Exceeded

Solution code:

while True:
    H = int(input())

    if H == 0:
        break

    W = H

    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] = 0
            else:
                table[i][j] = 1

    ans = 0

    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)

Submission status: Time Limit Exceeded

Solution code:

while True:
    H = int(input())

    if H == 0:
        break

    if H == 1:
        str = input()
        if str == ".":
            print(1)
        else:
            print(0)
    else:
        W = H

        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] = 0
                else:
                    table[i][j] = 1

        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)

Submission status: Time Limit Exceeded

Solution code:

while True:
    H = int(input())

    if H == 0:
        break

    if H == 1:
        str = input()
        if str == ".":
            print(1)
        else:
            print(0)
    else:
        W = H

        ans = 0

        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] = 0
                else:
                    table[i][j] = 1 + min(table[i-1][j-1],table[i][j-1],table[i-1][j])
                    ans = max(ans, table[i][j])

        print(ans)

Submission status: Time Limit Exceeded

Solution code:
while True:
    n = int(input())
    if n == 0:
        break
    inp = []
    for i in range(n):
        inp.append(list(input()))
    ans = 0
    for i in range(n):
        p = [(x, y) for x in range(n - i) for y in range(n - i)]
        for x, y in p:
            if inp[y][x] == ".":
                pp = [(xx, yy) for xx in range(x, x + i + 1) for yy in range(y, y + i + 1)]
                for xx, yy in pp:
                    if inp[yy][xx] == "*":
                        break
                else:
                    ans = i + 1
                    break
        else:
            continue
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
while True:
    n = int(input())
    if n == 0:
        break
    inp = []
    for i in range(n):
        inp.append(list(input()))
    ans = 0
    p_all = set([(x, y) for x in range(n) for y in range(n)])
    for i in range(n):
        p = [(x, y) for x in range(n - i) for y in range(n - i) if (x, y) in p_all]
        for x, y in p:
            if inp[y][x] == ".":
                pp = [(xx, yy) for xx in range(x, x + i + 1) for yy in range(y, y + i + 1)]
                for xx, yy in pp:
                    if inp[yy][xx] == "*":
                        p_all.remove((x, y))
                        break
                else:
                    ans = i + 1
                    break
        else:
            continue
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
while True:
    n = int(input())
    if n == 0:
        break
    inp = []
    for i in range(n):
        inp.append(list(input()))
    ans = 0
    for i in range(n)[::-1]:
        p = [(x, y) for x in range(n - i) for y in range(n - i)]
        for x, y in p:
            if inp[y][x] == ".":
                pp = [(xx, yy) for xx in range(x, x + i + 1) for yy in range(y, y + i + 1)]
                for xx, yy in pp:
                    if inp[yy][xx] == "*":
                        break
                else:
                    ans = i + 1
                    break
        else:
            continue
        break
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
while True:
    n = int(input())
    if n == 0:
        break
    inp = []
    for i in range(n):
        inp.append(list(input()))
    
    sum_dot = [[0 for i in range(n + 1)] for j in range(n + 1)]
    for y in range(n):
        for x in range(n):
            sum_dot[y + 1][x + 1] = sum_dot[y][x + 1] + inp[y][:x + 1].count(".")
    
    ans = 0
    for i in range(n)[::-1]:
        p = [(x, y) for y in range(n - i) for x in range(n - i)]
        for x, y in p:
            s = sum_dot[y + i + 1][x + i + 1] - sum_dot[y][x + i + 1] - sum_dot[y + i + 1][x] + sum_dot[y][x]
            if s == (i + 1)*(i + 1):
                ans = i + 1
                break
        else:
            continue
        break
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

while True:
    n = int(input())
    if n == 0:
        break
    inp = []
    for i in range(n):
        inp.append(list(input()))
    
    sum_dot = [[0 for i in range(n + 1)] for j in range(n + 1)]
    for y in range(n):
        for x in range(n):
            sum_dot[y + 1][x + 1] = sum_dot[y][x + 1] + inp[y][:x + 1].count(".")
    
    ans = 0
    for i in range(int(math.sqrt(sum_dot[-1][-1])))[::-1]:
        p = [(x, y) for y in range(n - i) for x in range(n - i)]
        for x, y in p:
            s = sum_dot[y + i + 1][x + i + 1] - sum_dot[y][x + i + 1] - sum_dot[y + i + 1][x] + sum_dot[y][x]
            if s == (i + 1)*(i + 1):
                ans = i + 1
                break
        else:
            continue
        break
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
while 1:
    n = int(raw_input())
    if n == 0:
        break
    dp = [[0] * n for i in range(n)]
    r = 0
    for i in range(n):
        for j, ch in enumerate(raw_input()):
            if ch == '*':
                continue
            dp[i][j] = 1
            if i >= 1 or j >= 1:
                for k in range(1, dp[i - 1][j - 1] + 1):
                    if dp[i - k][j] == 0 or dp[i][j - k] == 0:
                        break
                    dp[i][j] += 1
            r = max(r, dp[i][j])
    print r

Submission status: Time Limit Exceeded

Solution code:
while True:
    n = int(raw_input())
    r = 0
    if n == 0:
        break
    s = [map(int, raw_input().replace('.','0').replace('*','1')) for i in range(n)]
    sum = [[0] * (n + 1) for i in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            sum[i][j] += s[i - 1][j - 1]
            sum[i][j] += (sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1])
    for size in range(n, 0, -1):
        for i in range(size, n + 1):
            for j in range(size, n + 1):
                s = sum[i][j] - sum[i - size][j] - sum[i][j - size] + sum[i - size][j - size]
                if s == 0:
                    r = max(r, size)
                    break
    print r

Submission status: Time Limit Exceeded

Solution code:
def m(sum, n):
    for size in range(n, 0, -1):
        for i in range(size, n + 1):
            for j in range(size, n + 1):
                s = sum[i][j] - sum[i - size][j] - sum[i][j - size] + sum[i - size][j - size]
                if s == 0:
                    return size
    return 0

while True:
    n = int(raw_input())
    if n == 0:
        break
    s = [map(int, raw_input().replace('.','0').replace('*','1')) for i in range(n)]
    sum = [[0] * (n + 1) for i in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            sum[i][j] += s[i - 1][j - 1]
            sum[i][j] += (sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1])
    print m(sum, n)

Submission status: Time Limit Exceeded

Solution code:
def check(sum, i, j, size):
    s = sum[i][j] - sum[i - size][j] - sum[i][j - size] + sum[i - size][j - size]
    return s == 0

def mm(sum, n, size):
    for i in range(size, n + 1):
            for j in range(size, n + 1):
                if check(sum, i, j, size):
                    return True
    return False

def m(sum, n):
    r = 0
    left, mid, right = 0, 0, n
    while left <= right:
        mid = (left + right) / 2
        if mm(sum, n, mid):
            r = max(r, mid)
            left = mid + 1
        else:
            if left == right:
                break
            right = mid
    return r

while True:
    n = int(raw_input())
    if n == 0:
        break
    s = [map(int, raw_input().replace('.','0').replace('*','1')) for i in range(n)]
    sum = [[0] * (n + 1) for i in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            sum[i][j] += s[i - 1][j - 1]
            sum[i][j] += (sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1])
    print m(sum, n)

Submission status: Time Limit Exceeded

Solution code:
def check(sum, i, j, size):
    s = sum[i][j] - sum[i - size][j] - sum[i][j - size] + sum[i - size][j - size]
    return s == 0

def mm(sum, n, size):
    for i in xrange(size, n + 1):
            for j in xrange(size, n + 1):
                if check(sum, i, j, size):
                    return True
    return False

def m(sum, n):
    r = 0
    left, mid, right = 0, 0, n
    while left <= right:
        mid = (left + right) / 2
        if mm(sum, n, mid):
            r = max(r, mid)
            left = mid + 1
        else:
            if left == right:
                break
            right = mid
    return r

while True:
    n = int(raw_input())
    if n == 0:
        break
    s = [map(int, raw_input().replace('.','0').replace('*','1')) for i in xrange(n)]
    sum = [[0] * (n + 1) for i in xrange(n + 1)]
    for i in xrange(1, n + 1):
        for j in xrange(1, n + 1):
            sum[i][j] += s[i - 1][j - 1]
            sum[i][j] += (sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1])
    print m(sum, n)