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

Solution code:
while(1):
    n = int(input())
    if n == 0:
        break
    a = [0 for i in range(n)]
    b = [[0 for i in range(n)] for j in range(n)]
    c_ = [[100 for i in range(n)] for j in range(n)]
    c = [[100 for i in range(n)] for j in range(n)]
    for i in range(n):
        a[i] = [0 if i == "." else 1 for i in list(input())]
        for j in range(n):
            for k in range(j,n):
                b[i][j] = k-j
                if a[i][k] == 1:
                    break
    for col in range(n):
        for i in range(n):
            for j in range(i,n):
                min_ = min(c_[i][col], b[j][col])
                if min_ < j-i+1:
                    if c_[i][col] == 100:
                        c[i][col] = 0
                    break
                c_[i][col] = min_
                c[i][col] = j-i+1

    print(max([max(i) for i in c]))

Submission status: Wrong Answer

Solution code:
while(1):
    n = int(input())
    if n == 0:
        break
    a = [0 for i in range(n)]
    b = [[0 for i in range(n)] for j in range(n)]
    c_ = [[2000 for i in range(n)] for j in range(n)]
    c = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        a[i] = [0 if i == "." else 1 for i in list(input())]
        count = 0
        for j in range(n)[::-1]:
            if a[i] == 0:
                count += 1
                a[i] = count
            else:
                count = 0
                a[i] = count
                
    for col in range(n):
        for i in range(n):
            for j in range(i,n):
                min_ = min(c_[i][col], b[j][col])
                if min_ < j-i+1:
                    break
                c_[i][col] = min_
                c[i][col] = j-i+1
    
    print(max([max(i) for i in c]))

Submission status: Wrong Answer

Solution code:
while(1):
    n = int(input())
    if n == 0:
        break
    a = [0 for i in range(n)]
    b = [[0 for i in range(n)] for j in range(n)]
    c_ = [[2000 for i in range(n)] for j in range(n)]
    c = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        a[i] = [0 if i == "." else 1 for i in list(input())]
        count = 0
        for j in range(n)[::-1]:
            if a[i][j] == 0:
                count += 1
                a[i][j] = count
            else:
                count = 0
                a[i][j] = count
                
    for col in range(n):
        for i in range(n):
            for j in range(i,n):
                min_ = min(c_[i][col], b[j][col])
                if min_ < j-i+1:
                    break
                c_[i][col] = min_
                c[i][col] = j-i+1
    
    print(max([max(i) for i in c]))

Submission status: Wrong Answer

Solution code:
while(1):
    n = int(input())
    if n == 0:
        break
    a = [0 for i in range(n)]
    b = [[0 for i in range(n)] for j in range(n)]
    c_ = [[2000 for i in range(n)] for j in range(n)]
    c = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        a[i] = [0 if i == "." else 1 for i in list(input())]
        count = 0
        for j in range(n)[::-1]:
            if a[i][j] == 0:
                count += 1
                b[i][j] = count
            else:
                count = 0
                b[i][j] = count
                
    for col in range(n):
        for i in range(n):
            for j in range(i,n):
                min_ = min(c_[i][col], b[j][col])
                if min_ < j-i+1:
                    break
                c_[i][col] = min_
                c[i][col] = j-i+1
    
    print(*b,sep="\n")
    print(max([max(i) for i in c]))

Submission status: Wrong Answer

Solution code:
while(1):
    n = int(input())
    if n == 0:
        break
    a = [0 for i in range(n)]
    b = [[0 for i in range(n)] for j in range(n)]
    c_ = [[2000 for i in range(n)] for j in range(n)]
    c = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        a[i] = [0 if i == "." else 1 for i in list(input())]
        count = 0
        for j in range(n)[::-1]:
            if a[i][j] == 0:
                count += 1
                b[i][j] = count
            else:
                count = 0
                b[i][j] = count
                
    for col in range(n):
        for i in range(n):
            for j in range(i,n):
                min_ = min(c_[i][col], b[j][col])
                l = j-i-1
                if min_ < l:
                    break
                c_[i][col] = min_
                c[i][col] = l
    
    print(max([max(i) for i in c]))

Submission status: Wrong Answer

Solution code:
import sys

while 1:
  n=input()
  if n==0:break
  A=[raw_input()[:-1] for i in range(n)]
  B=[]
  for i in range(n):
    if '1' in A[i]: c=1
    else: c=0
    B.append(int(A[i].replace('.','1').replace('*','0'),2))
  C=B[:]

  for i in range(1,n):
    for j in range(n-i):
      B[j]&=B[j+1]
      if '1'*(i+1) in format(B[j],'b'): c=i+1
  print c

Submission status: Wrong Answer

Solution code:
import sys

while 1:
  n=input()
  if n==0:break
  A=[raw_input()[:-1] for i in range(n)]
  B=[]
  c=0
  for i in range(n):
    if c==0 and '1' in A[i]: c=1
    B.append(int(A[i].replace('.','1').replace('*','0'),2))
  C=B[:]

  for i in range(1,n):
    for j in range(n-i):
      B[j]&=B[j+1]
      if '1'*(i+1) in format(B[j],'b'): c=i+1
  print c

Submission status: Wrong Answer

Solution code:
import sys

while 1:
  n=input()+1
  if n==1:break
  A=[''*n]+[' '+raw_input() for i in range(1,n)]
  M=[[0]*n for i in range(n)]
  for i in range(1,n):
    a=M[i][0]
    for j in range(1,n):
      if A[i][j]=='.':
        a=min(M[i-1][j-1],M[i-1][j],a)+1
        M[i][j]=a
  print max(map(max,M))

Submission status: Wrong Answer

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 == ".":
                flag0=1
                dp[i][j]=1
            j+=1
    if flag0==0:
        print 0
    else:
        solve=1
        while True:
            flag=0
            for y in range(n-solve):
                for x in range(n-solve):
                    if dp[y][x]==solve:
                        dp[y][x]=min(dp[y+1][x],dp[y][x+1],dp[y+1][x+1])+1
                        flag=1
            if flag==0:
                break
            solve+=1
        print solve-1

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
while True:
    n=input()
    if n==0:
        break
    dp=[[0 for i in range(n)]for j in range(n)]
    flag0=0
    flag1=0
    for i in range(n):
        j=0
        for c in raw_input():
            if c == ".":
                flag0=1
                dp[i][j]=1
            if c == "*":
                flag1=1                
            j+=1
    if flag0==0:
        print "test"
        print 0
    elif flag1==0:
        print n
    else:
        solve=1
        while True:
            flag=0
            for y in range(n-solve):
                for x in range(n-solve):
                    if dp[y][x]==solve:
                        dp[y][x]=min(dp[y+1][x],dp[y][x+1],dp[y+1][x+1])+1
                        flag=1
            if flag==0:
                break
            solve+=1
        allmax=0
        for i in range(n):
            if allmax<max(dp[i]):
                allmax=max(dp[i])
        print allmax

Submission status: Wrong Answer

Solution code:
while True:
    n=input()
    if n==0:
        break
    dp=[[0 for i in range(n)]for j in range(n)]
    flag0=0
    flag1=0
    for i in range(n):
        j=0
        for c in raw_input():
            if c == ".":
                flag0=1
                dp[i][j]=1
            if c == "*":
                flag1=1                
            j+=1
    if flag0==0:
        print "test"
        print 0
    elif flag1==0:
        print n
    else:
        solve=1
        while True:
            flag=0
            for y in range(n-solve):
                for x in range(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: Wrong Answer

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]==1:
                            flag=1
            if flag==0:
                break
            solve+=1
        print solve

Submission status: Wrong Answer

Solution code:
while True:
    n=input()
    if n==0:
        break
    dp=[[0 for i in range(n+1)]for j in range(n+1)]
    for i in range(1,n+1):
        j=0
        line=" "+raw_input()
        for c in line:
            if c == ".":
                dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
            else:
                dp[i][j]=0
            j+=1
    allmax=0
    for i in range(n):
        if allmax<max(dp[i]):
            allmax=max(dp[i])
    print allmax

Submission status: Wrong Answer

Solution code:
while 1:
    n=int(raw_input())
    if n==0:
        break
    field=[raw_input() for i in range(n)]
    large=[[0]*(n+1) for i in range(n+1)]
    for i in range(n):
        for j in range(n):
            if field[i][j]=='.':
                large[i][j]=min(large[i][j-1],large[i-1][j],large[i-1][i-1])+1
    print max(map(max,large))

Submission status: Wrong Answer

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):
        for y in range(n - i):
            for x in range(n - i):
                if inp[y][x] == ".":
                    flag = True
                    for yy in range(y, y + i):
                        for xx in range(x, x + i):
                            if inp[yy][xx] == "*":
                                flag = False
                                break
                    if flag:
                        ans = i
                        break
            if flag:
                break
    print(ans)

Submission status: Wrong Answer

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)] for j in range(n + 1)]
    for y in range(1, n + 1):
        for x in range(n):
            sum_dot[y][x] = sum_dot[y - 1][x] + inp[y - 1][:x + 1].count(".")
    if sum_dot[n][n - 1] == n*n:
        print(n)
        continue
    for i in range(n)[::-1]:
        p = [(x, y) for x in range(n)[::-1] for y in range(n)[::-1]]
        for x, y in p:
            s = sum_dot[y + 1][x] - sum_dot[y - i + 1][x] - sum_dot[y + 1][x - i] + sum_dot[y - i + 1][x - i]
            if s == i*i:
                print(i)
                break
        else:
            continue
        break

Submission status: Wrong Answer

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)]
    p = [(x, y) for y in range(n) for x in range(i)]
    for x, y in p:
            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: Wrong Answer

Solution code:
while 1:
    n = int(raw_input())
    if n == 0:
        break
    dp = [[1] * n for i in range(n)]
    r = 1
    for i in range(n):
        for j, ch in enumerate(raw_input()):
            if ch == '*':
                dp[i][j] = 0
                continue
            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: Wrong Answer

Solution code:
while 1:
    n = int(raw_input())
    if n == 0:
        break
    dp = [[1] * n for i in range(n)]
    r = 0
    for i in range(n):
        for j, ch in enumerate(raw_input()):
            if ch == '*':
                dp[i][j] = 0
                continue
            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: Wrong Answer

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

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

Solution code:
n = int(raw_input())
s = [[] for i in range(n)]
flag = 0
for i in range(n):
    s[i] = raw_input()
for i in range(n,1,-1):
    for j in range(n-i+1):
        for k in range(n-i+1):
            out = ""
            for l in range(i):
                for m in range(i):
                    out += s[j+l][k+m]
            if out == "."*i:
                print i
                flag = 1
            if flag == 1: break
        if flag == 1: break
    if flag == 1: break

Submission status: Wrong Answer

Solution code:
n = int(raw_input())
s = [[] for i in range(n)]
flag = 0
for i in range(n):
    s[i] = raw_input()
for i in range(n,1,-1):
    for j in range(n-i+1):
        for k in range(n-i+1):
            out = ""
            for l in range(i):
                for m in range(i):
                    out += s[j+l][k+m]
            if out == "."*i**2:
                print i
                flag = 1
            if flag == 1: break
        if flag == 1: break
    if flag == 1: break

Submission status: Wrong Answer

Solution code:
n = int(raw_input())
s = [[] for i in range(n)]
flag = 0
for i in range(n):
    s[i] = raw_input()
for i in range(n,1,-1):
    for j in range(n-i+1):
        for k in range(n-i+1):
            out = ""
            for l in range(i):
                for m in range(i):
                    out += s[j+l][k+m]
            if out == "."*i*i:
                print i
                flag = 1
            if flag == 1: break
        if flag == 1: break
    if flag == 1: break
if flag == 0:
    print 1

Submission status: Wrong Answer

Solution code:
n = int(raw_input())
s = [[] for i in range(n)]
flag = 0
for i in range(n):
    s[i] = raw_input()
for i in range(n,1,-1):
    for j in range(n-i+1):
        for k in range(n-i+1):
            out = ""
            for l in range(i):
                for m in range(i):
                    out += s[j+l][k+m]
            if out.count("*") == 0:
                print i
                flag = 1
            if flag == 1: break
        if flag == 1: break
    if flag == 1: break
if flag == 0:
    print 1

Submission status: Wrong Answer

Solution code:
while True:
    n = int(raw_input())
    if n == 0:
        break
    s = [[] for i in range(n)]
    flag = 0
    for i in range(n):
        s[i] = raw_input()
    for i in range(n,1,-1):
        for j in range(n-i+1):
            for k in range(n-i+1):
                out = ""
                for l in range(i):
                    for m in range(i):
                        out += s[j+l][k+m]
                if out.count("*") == 0:
                    print i
                    flag = 1
                if flag == 1: break
            if flag == 1: break
        if flag == 1: break
    if flag == 0:
        print 1

Submission status: Wrong Answer

Solution code:
while True:
    n = int(raw_input())
    if n == 0:
        break
    s = [[] for i in range(n)]
    for i in range(n):
        s[i] = raw_input()
    for i in range(n,0,-1):
        for j in range(n-i+1):
            for k in range(n-i+1):
                flag = 0
                for l in range(i):
                    for m in range(i):
                        if s[j+l][k+m] == "*":
                            flag = 1
                            break
                if flag == 0:
                    print i
            if flag == 0: break
        if flag == 0: break
    if flag == 1:
        print 0

Submission status: Wrong Answer

Solution code:
while True:
	n = int(raw_input())
	if n == 0: break
	map = [raw_input() for i in range(n)]
	flag = 0
	for len in range(n,0,-1):
		for row in range(n-len+1):
			for sp in range(n-len+1):
				if map[row][sp:sp+len] == "."*len:
					for i in range(1,len):
						if map[row+i][sp:sp+len] != "."*len:
							break
					else:
						print len
						flag = 1
				if flag: break
			if flag: break
		if flag: break

Submission status: Wrong Answer

Solution code:
l = {".":1,"*":-1000}
def x(a):
	m=0
	for c in N:
		p=[0]*n 
		for e in range(c,n):
			d=e-c+1
			for r in N:
				p[r]+=l[a[r][e]]
			m=max(P(p,d),m)
	return int(m**0.5)
	
def P(a,d):
	m=0
	for i in range(n-d):
		k=sum(a[i:i+d])
		m=max(m,k)
	return m
    
while True:
	n=input()
	if n==0:break
	N=range(n)
	print x([raw_input() for i in N])

Submission status: Wrong Answer

Solution code:
l = {".":1,"*":-10000}
def x(a):
	m=0
	for c in N:
		p=[0]*n 
		for e in range(c,n):
			d=e-c+1
			for r in N:
				p[r]+=l[a[r][e]]
			m=max(P(p,d),m)
	return int(m**0.5)
	
def P(a,d):
	m=0
	for i in range(n-d):
		k=sum(a[i:i+d])
		m=max(m,k)
	return m
    
while True:
	n=input()
	if n==0:break
	elif n==1:print [raw_input()].count(".")
	N=range(n)
	print x([raw_input() for i in N])

Submission status: Wrong Answer

Solution code:
l = {".":1,"*":-10000}
def x(a):
	m=0
	for c in N:
		p=[0]*n 
		for e in range(c,n):
			d=e-c+1
			for r in N:
				p[r]+=l[a[r][e]]
			m=max(P(p,d),m)
	return int(m**0.5)
	
def P(a,d):
	m=0
	for i in range(n-d):
		k=sum(a[i:i+d])
		m=max(m,k)
	return m
    
while True:
	n=input()
	if n==0:break
	elif n==1:print [raw_input()].count(".")
	else:
		N=range(n)
		print x([raw_input() for i in N])

Submission status: Time Limit Exceeded

Solution code:
while(1):
    n = int(input())
    if n == 0:
        break
    a = [0 for i in range(n)]
    b = [[0 for i in range(n)] for j in range(n)]
    c_ = [[2000 for i in range(n)] for j in range(n)]
    size = [[0 for i in range(n)] for j in range(n)]
    c = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        a[i] = [0 if i == "." else 1 for i in list(input())]
        for j in range(n):
            for k in range(j,n):
                if a[i][k] == 1:
                    break
                b[i][j] = k-j+1
                
    for i in range(n):
        for j in range(n):
            size[i][j] = min(n-i,n-j)
    for col in range(n):
        for i in range(n):
            for j in range(i,n):
                min_ = min(c_[i][col], b[j][col])
                if min_ < j-i+1:
                    break
                c_[i][col] = min_
                c[i][col] = j-i+1
    
    print(max([max(i) for i in c]))

Submission status: Time Limit Exceeded

Solution code:
while(1):
    n = int(input())
    if n == 0:
        break
    a = [0 for i in range(n)]
    b = [[0 for i in range(n)] for j in range(n)]
    c_ = [[2000 for i in range(n)] for j in range(n)]
    c = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        a[i] = [0 if i == "." else 1 for i in list(input())]
        for j in range(n):
            for k in range(j,n):
                if a[i][k] == 1:
                    break
                b[i][j] = k-j+1
                
    for col in range(n):
        for i in range(n):
            for j in range(i,n):
                min_ = min(c_[i][col], b[j][col])
                if min_ < j-i+1:
                    break
                c_[i][col] = min_
                c[i][col] = j-i+1
    
    print(max([max(i) for i in c]))

Submission status: Time Limit Exceeded

Solution code:
while(1):
    n = int(input())
    if n == 0:
        break
    a = [0 for i in range(n)]
    b = [[0 for i in range(n)] for j in range(n)]
    c_ = [[2000 for i in range(n)] for j in range(n)]
    c = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        a[i] = [0 if i == "." else 1 for i in list(input())]
        count = 0
        for j in range(n)[::-1]:
            if a[i][j] == 0:
                count += 1
                b[i][j] = count
            else:
                count = 0
                b[i][j] = count
                
    for col in range(n):
        for i in range(n):
            for j in range(i,n):
                min_ = min(c_[i][col], b[j][col])
                if min_ < j-i+1:
                    break
                c_[i][col] = min_
                c[i][col] = j-i+1
    
    print(max([max(i) for i in c]))

Submission status: Time Limit Exceeded

Solution code:
while(1):
    n = int(input())
    if n == 0:
        break
    a = [0 for i in range(n)]
    b = [[0 for i in range(n)] for j in range(n)]
    c_ = [[2000 for i in range(n)] for j in range(n)]
    c = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        a[i] = [0 if i == "." else 1 for i in list(input())]
        count = 0
        for j in range(n)[::-1]:
            if a[i][j] == 0:
                count += 1
                b[i][j] = count
            else:
                count = 0
                b[i][j] = count
                
    for col in range(n):
        for i in range(n):
            for j in range(i,n):
                min_ = min(c_[i][col], b[j][col])
                l = j-i+1
                if min_ < l:
                    break
                c_[i][col] = min_
                c[i][col] = l
    
    print(max([max(i) for i in c]))

Submission status: Time Limit Exceeded

Solution code:
while(1):
    n = int(input())
    if n == 0:
        break
    a = [0 for i in range(n)]
    b = [[0 for i in range(n)] for j in range(n)]
    c_ = [[2000 for i in range(n)] for j in range(n)]
    c = [[0 for i in range(n)] for j in range(n)]
    for i in range(n):
        a[i] = [0 if i == "." else 1 for i in list(input())]
        count = 0
        for j in range(n)[::-1]:
            if a[i][j] == 0:
                count += 1
                b[i][j] = count
            else:
                count = 0
                b[i][j] = count
                
    for col in range(n):
        for i in range(n):
            for j in range(i,n):
                if b[j][col] < c_[i][col]:
                    c_[i][col] = b[j][col]
                l = j-i+1
                if c_[i][col] < l:
                    break
                c[i][col] = l
    
    print(max([max(i) for i in c]))

Submission status: Time Limit Exceeded

Solution code:
import sys

while 1:
  n=input()
  if n==0:break
  A=[raw_input() for i in range(n)]
  B=[]
  c=0
  for i in range(n):
    if c==0 and '1' in A[i]: c=1
    B.append(int(A[i].replace('.','1').replace('*','0'),2))
  C=B[:]
  for i in range(1,n):
    for j in range(n-i):
      B[j]&=B[j+1]
      if '1'*(i+1) in format(B[j],'b'): c=i+1
  print c

Submission status: Time Limit Exceeded

Solution code:
import sys

while 1:
  n=input()
  if n==0:break
  A=[raw_input() for i in range(n)]
  B=[]
  c=0
  for i in range(n):
    if c==0 and '1' in A[i]: c=1
    B.append(int(A[i].replace('.','1').replace('*','0'),2))
  C=B[:]
  for i in range(1,n):
    for j in range(n-i):
      B[j]&=B[j+1]
      if '1'*(i+1) in format(B[j],'b'): c=i+1
    if c!=i+1: break
  print c

Submission status: Time Limit Exceeded

Solution code:
while True:
    n = input()
    if n==0:
        break
    data=[]
    for i in range(n):
        data.append(raw_input())
    solve=0
    for i in range(n):
        if i+solve<n:
            for j in range(n):
                if j+solve<n:
                    while True:
                        flag=0
                        for a in range(solve+1):
                            for b in range(solve+1):
                                if data[i+a][j+b]=="*":
                                    flag=1
                                    break
                            if flag==1:
                                break
                        if flag==0:
                            solve+=1
                            if i+solve>=n or j+solve>=n: 
                                break
                        else:
                            break
                else:
                    break
        else:
            break
    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)]
    for i in range(n):
        j=0
        for c in raw_input():
            if c == ".":
                dp[i][j]=1
            j+=1
    while True:
        flag=0
        for y in range(n-1):
            for x in range(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
    allmax=0
    for i in range(n):
        if allmax<max(dp[i]):
            allmax=max(dp[i])
    print allmax

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 == ".":
                flag0=1
                dp[i][j]=1
            j+=1
    if flag0==0:
        print 0
    else:
        solve=1
        while True:
            flag=0
            for y in range(n-1):
                for x in range(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 == ".":
                flag0=1
                dp[i][j]=1
            j+=1
    if flag0==0:
        print 0
    else:
        solve=1
        while True:
            flag=0
            for y in range(n-solve):
                for x in range(n-solve):
                    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 range(n-solve):
                for x in range(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