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 = 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,0,-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 0

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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+1):
		k = 0
		for j in range(d):
			k+=a[i+j]
			if k<0:break
		else:
			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: Accepted

Solution code:
import sys

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

Submission status: Accepted

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):
    for j in range(1,n):
      if A[i][j]=='.': M[i][j]=min(M[i-1][j-1],M[i-1][j],M[i][j-1])+1
  print max(map(max,M))

Submission status: Accepted

Solution code:
import sys

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

Submission status: Accepted

Solution code:
import sys

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

Submission status: Accepted

Solution code:
import sys

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

Submission status: Accepted

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
    for i in range(1,n):
        for j in range(1,n):
            if dp[i][j]==1:
                dp[i][j]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
    allmax=0
    for i in range(n):
        if allmax<max(dp[i]):
            allmax=max(dp[i])
    print allmax

Submission status: Accepted

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
            j+=1
    allmax=0
    for i in range(n+1):
        if allmax<max(dp[i]):
            allmax=max(dp[i])
    print allmax

Submission status: Accepted

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][j-1])+1
    print max(map(max,large))

Submission status: Accepted

Solution code:
while True:
    Sei = []
    m_si = 0
    n = int(input())
    
    if n == 0:
        break
    for i in range(n):
        sen = input()
        Sei.append(list(sen))
   
    DP = [[0] * n for i in range(n)]
    for j in range(n):
        if Sei[0][j] == ".":
            DP[0][j] = 1
        else:
            DP[0][j] = 0
    for k in range(n):
        if Sei[k][0] == ".":
            DP[k][0] = 1
        else:
            DP[k][0] = 0
    for k in range(1,n):
        for l in range(1,n):
            if Sei[k][l] == ".":
                DP[k][l] = min(DP[k - 1][l],DP[k][l - 1],DP[k -1][l - 1]) + 1
            else:
                DP[k][l] = 0
    for i in range(n):
        if max(DP[i]) > m_si:
            m_si = max(DP[i])
    print(m_si)

Submission status: Accepted

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]

    prev_row = lmap[0]
    for curr_row in lmap[1:]:
        for x in range(1, len(lmap[0])):
            if curr_row[x] == 1:
                if prev_row[x-1] != 0 and prev_row[x] != 0 and curr_row[x-1] != 0:
                    curr_row[x] = min(prev_row[x-1], min(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 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: Accepted

Solution code:
import sys


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

    # ????±?????????????????????????????????£????????????????????£?????¢????¢??????§??????????????§????????????
    for y in range(1, len(lmap)):
        for x in range(1, len(lmap[0])):
            if lmap[y][x] == 1:
                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: Accepted

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 = []
        for c in row:
            if c == '.':
                temp.append(1)
            else:
                temp.append(0)
        lmap.append(temp)

    prev_row = lmap[0]
    for curr_row in lmap[1:]:
        for x in range(1, len(lmap[0])):
            if curr_row[x] == 1:
                if prev_row[x-1] != 0 and prev_row[x] != 0 and curr_row[x-1] != 0:
                    curr_row[x] = min(prev_row[x-1], min(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_square2(data):
    max_size = 0
    lmap = []
    for row in data:
        temp = []
        for c in row:
            if c == '.':
                temp.append(1)
            else:
                temp.append(0)
        lmap.append(temp)

    prev_row = lmap[0]
    for curr_row in lmap[1:]:
        for x, t in enumerate(curr_row[1:], start=1):
            if t == 1:
                curr_row[x] = min(prev_row[x-1], min(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 main(args):
    while True:
        n = int(input())
        if n == 0:
            break
        data = [input() for _ in range(n)]
        result = find_square2(data)
        print(result)


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

Submission status: Accepted

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


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

    # ????±?????????????????????????????????£????????????????????£?????¢????¢??????§??????????????§????????????
    for y in range(1, len(lmap)):
        for x in range(1, len(lmap[0])):
            if lmap[y][x] == 1:
                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 find_square(data):
    max_size = 0
    lmap = []
    for row in data:
        temp = []
        for c in row:
            if c == '.':
                temp.append(1)
            else:
                temp.append(0)
        lmap.append(temp)

    prev_row = lmap[0]
    for curr_row in lmap[1:]:
        for x in range(1, len(lmap[0])):
            if curr_row[x] == 1:
                if prev_row[x-1] != 0 and prev_row[x] != 0 and curr_row[x-1] != 0: #  ???????????¶?????????
                    curr_row[x] = min(prev_row[x-1], min(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_square2(data):
    max_size = 0
    lmap = [] # dp??¨???2?¬??????????
    # '.'????????????0??????'*'????????????1????????????
    for row in data:
        temp = []
        for c in row:
            if c == '.':
                temp.append(1)
            else:
                temp.append(0)
        lmap.append(temp)

    # ????±?????????????????????????????????£????????????????????£?????¢????¢??????§??????????????§????????????
    # (?????¨???(curr_row)??¨???????????????(prev_row)????????¢????????????????????§?????????????????????)
    prev_row = lmap[0]
    for curr_row in lmap[1:]:
        for x, t in enumerate(curr_row[1:], start=1):
            if t == 1:
                curr_row[x] = min(prev_row[x-1], min(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
    lmap = [array('B', [0]*len(data[0])) for _ in range(len(data))]
    # '.'????????????0??????'*'????????????1????????????
    for row in data:
        temp = []
        for c in row:
            if c == '.':
                temp.append(1)
            else:
                temp.append(0)
        lmap.append(temp)

    # ????±?????????????????????????????????£????????????????????£?????¢????¢??????§??????????????§????????????
    # (?????¨???(curr_row)??¨???????????????(prev_row)????????¢????????????????????§?????????????????????)
    prev_row = lmap[0]
    for curr_row in lmap[1:]:
        for x, t in enumerate(curr_row[1:], start=1):
            if t == 1:
                curr_row[x] = min(prev_row[x-1], min(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 main(args):
    while True:
        n = int(input())
        if n == 0:
            break
        data = [input() for _ in range(n)]
        result = find_square3(data)
        print(result)


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

Submission status: Accepted

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


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

    # ????±?????????????????????????????????£????????????????????£?????¢????¢??????§??????????????§????????????
    for y in range(1, len(lmap)):
        for x in range(1, len(lmap[0])):
            if lmap[y][x] == 1:
                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 find_square(data):
    max_size = 0
    lmap = []
    for row in data:
        temp = []
        for c in row:
            if c == '.':
                temp.append(1)
            else:
                temp.append(0)
        lmap.append(temp)

    prev_row = lmap[0]
    for curr_row in lmap[1:]:
        for x in range(1, len(lmap[0])):
            if curr_row[x] == 1:
                if prev_row[x-1] != 0 and prev_row[x] != 0 and curr_row[x-1] != 0: #  ???????????¶?????????
                    curr_row[x] = min(prev_row[x-1], min(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_square2(data):
    max_size = 0
    lmap = [] # dp??¨???2?¬??????????
    # '.'????????????0??????'*'????????????1????????????
    for row in data:
        temp = []
        for c in row:
            if c == '.':
                temp.append(1)
            else:
                temp.append(0)
        lmap.append(temp)

    # ????±?????????????????????????????????£????????????????????£?????¢????¢??????§??????????????§????????????
    # (?????¨???(curr_row)??¨???????????????(prev_row)????????¢????????????????????§?????????????????????)
    prev_row = lmap[0]
    for curr_row in lmap[1:]:
        for x, t in enumerate(curr_row[1:], start=1):
            if t == 1:
                curr_row[x] = min(prev_row[x-1], min(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
    lmap = [array('I', [0]*len(data[0])) for _ in range(len(data))]
    # '.'????????????0??????'*'????????????1????????????
    for y, row in enumerate(data):
        for x, c in enumerate(row):
            if c == '.':
                lmap[y][x] = 1

    # ????±?????????????????????????????????£????????????????????£?????¢????¢??????§??????????????§????????????
    # (?????¨???(curr_row)??¨???????????????(prev_row)????????¢????????????????????§?????????????????????)
    prev_row = lmap[0]
    for curr_row in lmap[1:]:
        for x, t in enumerate(curr_row[1:], start=1):
            if t == 1:
                curr_row[x] = min(prev_row[x-1], min(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 main(args):
    while True:
        n = int(input())
        if n == 0:
            break
        data = [input() for _ in range(n)]
        result = find_square3(data)
        print(result)


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

Submission status: Accepted

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


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

    # ????±?????????????????????????????????£????????????????????£?????¢????¢??????§??????????????§????????????
    for y in range(1, len(lmap)):
        for x in range(1, len(lmap[0])):
            if lmap[y][x] == 1:
                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 find_square(data):
    max_size = 0
    lmap = []
    for row in data:
        temp = []
        for c in row:
            if c == '.':
                temp.append(1)
            else:
                temp.append(0)
        lmap.append(temp)

    prev_row = lmap[0]
    for curr_row in lmap[1:]:
        for x in range(1, len(lmap[0])):
            if curr_row[x] == 1:
                if prev_row[x-1] != 0 and prev_row[x] != 0 and curr_row[x-1] != 0: #  ???????????¶?????????
                    curr_row[x] = min(prev_row[x-1], min(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_square2(data):
    max_size = 0
    lmap = [[0]*len(data[0]) for _ in range(len(data))] # dp??¨???2?¬??????????
    # '.'????????????1??????'*'????????????0????????????
    for y, row in enumerate(data):
        for x, c in enumerate(row):
            if c == '.':
                lmap[y][x] = 1

    # ????±?????????????????????????????????£????????????????????£?????¢????¢??????§??????????????§????????????
    # (?????¨???(curr_row)??¨???????????????(prev_row)????????¢????????????????????§?????????????????????)
    prev_row = lmap[0]
    for curr_row in lmap[1:]:
        for x, t in enumerate(curr_row[1:], start=1):
            if t == 1:
                curr_row[x] = min(prev_row[x-1], min(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
    lmap = [array('I', [0]*len(data[0])) for _ in range(len(data))]
    # '.'????????????1??????'*'????????????0????????????
    for y, row in enumerate(data):
        for x, c in enumerate(row):
            if c == '.':
                lmap[y][x] = 1

    # ????±?????????????????????????????????£????????????????????£?????¢????¢??????§??????????????§????????????
    # (?????¨???(curr_row)??¨???????????????(prev_row)????????¢????????????????????§?????????????????????)
    prev_row = lmap[0]
    for curr_row in lmap[1:]:
        for x, t in enumerate(curr_row[1:], start=1):
            if t == 1:
                curr_row[x] = min(prev_row[x-1], min(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 main(args):
    while True:
        n = int(input())
        if n == 0:
            break
        data = [input() for _ in range(n)]
        result = find_square2(data)
        print(result)


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

Submission status: Accepted

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


def find_square2(data):
    max_size = 0
    dp = [[0]*len(data[0]) for _ in range(len(data))] # dp??¨???2?¬??????????
    # '.'????????????1??????'*'????????????0????????????
    for y, row in enumerate(data):
        for x, c in enumerate(row):
            if c == '.':
                dp[y][x] = 1
                max_size = 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 main(args):
    while True:
        n = int(input())
        if n == 0:
            break
        data = [input() for _ in range(n)]
        result = find_square2(data)
        print(result)


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

Submission status: Accepted

Solution code:
import sys

while True:
    N = int(sys.stdin.readline().rstrip())
    if N == 0:
        break;
    max_value = 0
    prev_row = [0] * N
    for i in range(N):
        row = sys.stdin.readline().rstrip()
        curr_row = [0] * N
        for x,d in enumerate(row):
            if d == '.':
                if x == 0:
                    curr_row[x] = 1
                else:
                    curr_row[x] = min(prev_row[x-1], prev_row[x], curr_row[x-1]) + 1
        max_value = max(max(curr_row), max_value)
        prev_row = curr_row

    print(max_value)

Submission status: Accepted

Solution code:
import sys

while True:
    N = int(sys.stdin.readline().rstrip())
    if N == 0:
        break;
    max_value = 0
    prev_row = [0] * (N+1)
    for i in range(N):
        row = sys.stdin.readline().rstrip()
        curr_row = [0] * (N+1)
        for x,d in enumerate(row,1):
            if d == '.':
                curr_row[x] = min(prev_row[x-1], prev_row[x], curr_row[x-1]) + 1
        max_value = max(max(curr_row), max_value)
        prev_row = curr_row

    print(max_value)

Submission status: Accepted

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


def find_square0(data):
    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):
    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):
    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 main(args):
    while True:
        n = int(input())
        if n == 0:
            break
        data = [input() for _ in range(n)]
        result = find_square4(data)
        print(result)


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

Submission status: Accepted

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


def find_square0(data):
    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):
    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 main(args):
    while True:
        n = int(input())
        if n == 0:
            break
        data = [input() for _ in range(n)]
        result = find_square0(data)
        print(result)


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