Problem:


長方形探索

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

入力データは 1 行 W 文字から構成され、H 行が与えられます。たとえば以下のようなデータが与えられます。

..*....**.
..........
**....***.
....*.....
..*.......
...**.....
.*.*......
..........
..**......
.*..*.....

 入力データの一行が、一行のマス目を表現します。入力データの文字列のうち、. (ピリオド) は印のついていないマス目、* (アスタリスク) は印のついているマス目を示しています。入力データの文字列には、ピリオド、アスタリスク、改行以外の文字は含まれません。

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

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

よって、35 と出力すれば正解になります。なお、すべてのマス目に印がついている場合には、0 を出力してください。

Input

複数のデータセットが与えられます。各データセットはスペースで区切られた H と W からなる行から始まり、つづいて H &times; W の長方形が与えられます。H, W はともに 500　以下とします。

入力は２つの 0 を含む行で終わります。データセットの数は 20 を超えません。

Output

各データセットごとに、最大の長方形の面積を１行に出力してください。

Sample Input

10 10
...*....**
..........
**....**..
........*.
..*.......
**........
.*........
..........
....*..***
.*....*...
10 10
..*....*..
.*.*...*..
*****..*..
*...*..*..
*...*..*..
..........
****.*...*
..*..*...*
.*...*...*
****..***.
2 3
...
...
0 0

Output for the Sample Input

28
12
6



Sample input:
10 10
...*....**
..........
**....**..
........*.
..*.......
**........
.*........
..........
....*..***
.*....*...
10 10
..*....*..
.*.*...*..
*****..*..
*...*..*..
*...*..*..
..........
****.*...*
..*..*...*
.*...*...*
****..***.
2 3
...
...
0 0


Sample output:
28
12
6

Submission status: Wrong Answer

Solution code:
# ref: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=924554#1
from itertools import product
while(True):
    H,W = map(int,input().split())
    if not H: break
    ma = [list(map(int,input().replace(".","1").replace("*","0")))+[0] for _ in range(H)]
    for i,j in product(range(1,H),range(W)):
        if ma[i][j]: ma[i][j] += ma[i-1][j]
    ans = 0
    for i in range(H):
        stk = []
        for j in range(W+1):
            cur = ma[i][j]
            if (not stk) or stk[-1][1] < cur:
                stk.append([j,cur])
            elif stk[-1][1] > cur:
                idx = j
                while stk and stk[-1][1] >= cur:
                    ans = max(ans,stk[-1][1]*(j-stk[-1][0]))
                    stk.pop()
    print(ans)

Submission status: Wrong Answer

Solution code:
while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  H = range(h)
  A = [0]*h
  for i in H:
    x = raw_input().replace(".", "1").replace("*", "0")
    A[i] = map(int, list(x))
  B = A[:]
  C = [0]*h
  for j in H[1:]:
    M = ["1","11","111"]
#    for i in H[j:]:
#      x = [e1 & e2 for e1, e2 in zip(B[i-j], A[i])]
#      B[i-j] = x
#      M.append(sorted("".join(map(str, x)).split("0"))[-1])
    C[j] = len(sorted(M)[-1])*(j+1)
  print max(C)

Submission status: Wrong Answer

Solution code:
def f(k): return max(M[k],j-C[k])
while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  H = range(h)
  W = range(w)
  W0 = [0]*w
  C = [0]*(h+1)
  M = C[:]
  a=W0
  for i in H:
    x = raw_input()
    b = W0
    sp=-1
    C = [-1]*(h+1)
    for j in W:
      if x[j]=="*": c=0
      elif x[j]==".": c=a[j]+1
      b[j] = c
      w1 = c-sp
      if c>sp: C[sp+1:c+1]=[j]*(w1)
      elif c<sp:
        for k in range(c+1,sp+1): M[k]=f(k)
        C[c+1:sp+1]=[-1]*(-w1)
      sp=c
    for k in W[:sp+1]:
      if C[k]>=0: M[k]=f(k)
    a=b
  s=max([a*b for a,b in zip(M, H+[h])])
  print s

Submission status: Wrong Answer

Solution code:
def f(k): return max(M[k],j-C[k])
while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  H = range(h)
  W = range(w)
  W0 = [0]*w
  C = [0]*(h+1)
  M = C[:]
  a=W0[:]
  for i in H:
    x = raw_input()
    b = W0[:]
    sp=-1
    C = [-1]*(h+1)
    for j in W:
      if x[j]=="*": c=0
      elif x[j]==".": c=a[j]+1
      b[j] = c
      w1 = c-sp
      if c>sp: C[sp+1:c+1]=[j]*(w1)
      elif c<sp:
        for k in range(c+1,sp+1): M[k]=f(k)
        C[c+1:sp+1]=[-1]*(-w1)
      sp=c
    for k in W[:sp+1]:
      if C[k]>=0: M[k]=f(k)
    a=b
  s=max([a*b for a,b in zip(M, H+[h])])
  print s

Submission status: Wrong Answer

Solution code:
def f(j): return [0,a[j]+1][x[j]=="."]

while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  M = [-1]*(h+1)
  a = [0]*w
  for i in range(h):
    x = raw_input()
    b = [0]*w
    sp = -1
    C = [-1]*(h+1)
    for j in range(w):
      b[j] = c = f(j)
      dw = c-sp
      if dw>0: C[sp+1:c+1]=[j]*dw
      elif dw<0:
        for k in range(c+1,sp+1): M[k]=max(M[k],j-C[k])
        C[c+1:sp+1]=[-1]*(-dw)
      sp=c
    for k in range(1,sp+1):
      if C[k]>=0: M[k]=max(M[k],w-C[k])
    a=b
  print max([a*b for a,b in zip(M, range(1,h+1))])

Submission status: Wrong Answer

Solution code:
def f(x,a):
  f=0
  if x==".": f=a+1
  return f

while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  M = [-1]*(h+1)
  a = [0]*w
  for i in range(h):
    x = raw_input()
    b = [0]*w
    sp = -1
    C = [-1]*(h+1)
    for j in range(w):
      b[j] = c = f(x[j],a[j])
      dw = c-sp
      if dw>0: C[sp+1:c+1]=[j]*dw
      elif dw<0:
        for k in range(c+1,sp+1): M[k]=max(M[k],j-C[k])
        C[c+1:sp+1]=[-1]*(-dw)
      sp=c
    for k in range(1,sp+1):
      if C[k]>=0: M[k]=max(M[k],w-C[k])
    a=b
  print max([a*b for a,b in zip(M, range(1,h+1))])

Submission status: Wrong Answer

Solution code:
while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  M = [-1]*(h+1)
  a = [0]*w
  for i in range(h):
    x = raw_input()
    b = [0]*w
    sp = -1
    C = [-1]*(h+1)
    for j in range(w):
      if x[j]==".": c = a[j]+1
      else: c = 0
      b[j] = c
      dw = c-sp
      if dw>0: C[sp+1:c+1]=[j]*dw
      elif dw<0:
        for k in range(c+1,sp+1): M[k]=max(M[k],j-C[k])
        C[c+1:sp+1]=[-1]*(-dw)
      sp=c
    for k in range(1,sp+1):
      if C[k]>=0: M[k]=max(M[k],w-C[k])
    a=b
  print max([a*b for a,b in zip(M, range(1,h+1))])

Submission status: Wrong Answer

Solution code:
import re
while True:
    H, W = map(int, input().split())
    if H == 0:
        break
    s = ''.join([input() for _ in range(H)])
    maxv = 0
    for it in re.finditer('[.]+', s):
        a, b = it.start(0), it.end(0)
        edge = s[a:b]
        i = 0
        while s[a:b] == edge:
            a += H
            b += H
            i += 1
        maxv = max(maxv, i*len(edge))
    print(maxv)

Submission status: Wrong Answer

Solution code:
def solve(field,H,W):
    space = [[0]*(W+1) for _ in xrange(H)]
    for x in xrange(W-1,-1,-1):
        for y in xrange(H):
            if field[y][x]==".":
                space[y][x] = space[y][x+1]+1 
    ans = 0
    for x in xrange(W):
        for y in (yy for yy in xrange(H) if field[y][x] == "."):
            mi = 2 << 20
            for h in xrange(y,H):
                if(field[h][x] == "*"):
                    break
                mi = min(mi, space[h][x])
                ans = max(ans, mi*(h-y+1))
            if ans > (W-x)*(H-y):
                return ans
    return ans

while True:
    H,W = map(int, raw_input().split(" "))
    if (H,W) == (0,0):
        break
    field = [raw_input() for _ in xrange(H)]
    print solve(field,H,W)

Submission status: Wrong Answer

Solution code:
def fill0(s,x,y):
	A[y][x] = 0
	if x < W-1 and A[y][x+1] == s: fill0(s,x+1,y)
	if y < H-1 and A[y+1][x] == s: fill0(s,x,y+1)
	if x > 0   and A[y][x-1] == s: fill0(s,x-1,y)
	if y > 0   and A[y-1][x] == s: fill0(s,x,y-1)

while 1:
	H,W = map(int,raw_input().split())
	if H == 0: break
	A = [list(raw_input()) for i in range(H)]
	i = 0
	for y in range(H):
		for x in range(W):
			if A[y][x] in ["#","@","*"]:
				fill0(A[y][x],x,y)
				i += 1
	print i

Submission status: Wrong Answer

Solution code:
def fill0(A,s,x,y):
	A[y][x] = 0
	if x < W-1 and A[y][x+1] == s: fill0(A,s,x+1,y)
	if y < H-1 and A[y+1][x] == s: fill0(A,s,x,y+1)
	if x > 0   and A[y][x-1] == s: fill0(A,s,x-1,y)
	if y > 0   and A[y-1][x] == s: fill0(A,s,x,y-1)

while 1:
	H,W = map(int,raw_input().split())
	if H == 0: break
	A = [list(raw_input()) for i in range(H)]
	ans = 0
	for y in range(H):
		for x in range(W):
			if A[y][x] in ["#","@","*"]:
				fill0(A,A[y][x],x,y)
				ans += 1
	print ans

Submission status: Wrong Answer

Solution code:
while 1:
	H,W = map(int,raw_input().split())
	if H == 0: break
	M = [raw_input() for i in range(H)]
	if sum([M[h].count(".") for h in range(H)]) == 0:
		print 0
		continue
	A = [[0]*W for i in range(H)]
	B = [[0]*W for i in range(H)]
	ans = 1
	for h in range(H):
		L = 0
		for w in range(W):
			if M[h][w] == ".":
				L += 1
			else:
				L = 0
			A[h][w] = L
			B[h][w] = (B[h-1][w] if h > 0 else 0) + 1 if L > 0 else 0
			if L*B[h][w] > ans:
				a = min([A[h-i][w] for i in range(ans/B[h][w]+1)])
				for hi in range(ans/L,B[h][w]):
					a = min(a,A[h-hi][w])
					if a*B[h][w] <= ans:
						break
					ans = max(ans,a*(hi+1))
	print ans

Submission status: Wrong Answer

Solution code:
while 1:
	H,W = map(int,raw_input().split())
	if H == 0: break
	M = [raw_input() for i in range(H)]
	if sum([M[h].count(".") for h in range(H)]) == 0:
		print 0
		continue
	A = [[0]*W for i in range(H)]
	B = [[0]*W for i in range(H)]
	ans = 1
	for h in range(H):
		L = 0
		for w in range(W):
			if M[h][w] == ".":
				L += 1
			else:
				L = 0
			A[h][w] = L
			B[h][w] = (B[h-1][w] if h > 0 else 0) + 1 if L > 0 else 0
			if L*B[h][w] > ans:
				a = min([A[h-i][w] for i in range(ans/L+1)])
				if a == 0: break
				for hi in range(ans/a,B[h][w]):
					a = min(a,A[h-hi][w])
					if a*B[h][w] <= ans:
						break
					ans = max(ans,a*(hi+1))
	print ans

Submission status: Wrong Answer

Solution code:
while 1:
	H,W = map(int,raw_input().split())
	if H == 0: break
	M = [raw_input() for i in range(H)]
	if sum([M[h].count(".") for h in range(H)]) == 0:
		print 0
		continue
	A = [[0]*W for i in range(H)]
	B = [[0]*W for i in range(H)]
	ans = 1
	for h in range(H):
		L = 0
		for w in range(W):
			if M[h][w] == ".":
				L += 1
			else:
				L = 0
			A[h][w] = L
			B[h][w] = (B[h-1][w] if h > 0 else 0) + 1 if L > 0 else 0
			if L*B[h][w] > ans:
				try: a = min([A[h-i-1][w] for i in range(ans/L)])
				except: a = L
				for hi in range(ans/a,B[h][w]):
					a = min(a,A[h-hi][w])
					if a*B[h][w] <= ans:
						break
					ans = max(ans,a*(hi+1))
	print ans

Submission status: Wrong Answer

Solution code:
while 1:
	H,W = map(int,raw_input().split())
	if H == 0: break
	M = [raw_input() for i in range(H)]
	A = [[0]*W for i in range(H)]
	B = [[0]*W for i in range(H)]
	ans = 0
	for h in range(H):
		L = 0
		for w in range(W):
			if M[h][w] == ".":
				L += 1
			else:
				L = 0
			A[h][w] = L
			B[h][w] = (B[h-1][w] if h > 0 else 0) + 1 if L > 0 else 0
			if L*B[h][w] > ans:
				a = min([A[h-i][w] for i in range(ans/L+1)])
				for hi in range(ans/a,B[h][w]):
					a = min(a,A[h-hi][w])
					if a*B[h][w] <= ans:
						break
					ans = max(ans,a*(hi+1))
	print ans

Submission status: Wrong Answer

Solution code:
while 1:
	H,W = map(int,raw_input().split())
	if H == 0: break
	M = [raw_input() for i in range(H)]
	A = [[0]*W for i in range(H)]
	B = [[0]*W for i in range(H)]
	ans = 0
	for h in range(H):
		L = 0
		for w in range(W):
			if M[h][w] == ".":
				L += 1
			else:
				L = 0
			A[h][w] = L
			B[h][w] = (B[h-1][w] if h > 0 else 0) + 1 if L > 0 else 0
			if L*B[h][w] > ans:
				a = min([A[h-i][w] for i in range(ans/L+1)])
				for hi in range(max(0,ans/a-1),B[h][w]):
					a = min(a,A[h-hi][w])
					if a*B[h][w] <= ans:
						break
					ans = max(ans,a*(hi+1))
	print ans

Submission status: Wrong Answer

Solution code:
while 1:
	H,W = map(int,raw_input().split())
	if H == 0: break
	M = [raw_input() for i in range(H)]
	A = [[0]*W for i in range(H)]
	B = [[0]*W for i in range(H)]
	ans = 0
	for h in range(H):
		L = 0
		for w in range(W):
			if M[h][w] == ".":
				L += 1
			else:
				L = 0
			A[h][w] = L
			B[h][w] = (B[h-1][w] if h > 0 else 0) + 1 if L > 0 else 0
			if L*B[h][w] > ans:
				a = min([A[h-i][w] for i in range(ans/L+1)])
				for hi in range(max(0,ans/a-2),B[h][w]):
					a = min(a,A[h-hi][w])
					if a*B[h][w] <= ans:
						break
					ans = max(ans,a*(hi+1))
	print ans

Submission status: Wrong Answer

Solution code:
while 1:
	H,W = map(int,raw_input().split())
	if H == 0: break
	M = [raw_input() for i in range(H)]
	A = [[0]*W for i in range(H)]
	B = [[0]*W for i in range(H)]
	ans = 0
	for h in range(H):
		L = 0
		for w in range(W):
			if M[h][w] == ".":
				L += 1
			else:
				L = 0
			A[h][w] = L
			B[h][w] = (B[h-1][w] if h > 0 else 0) + 1 if L > 0 else 0
			if L*B[h][w] > ans:
				a = min([A[h-i][w] for i in range(ans/L+1)])
				for hi in range(max(0,ans/a-3),B[h][w]):
					a = min(a,A[h-hi][w])
					if a*B[h][w] <= ans:
						break
					ans = max(ans,a*(hi+1))
	print ans

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
while(True):
    H,W = map(int,input().split())
    if not H: break
    ma = 0
    for i in range(H):
        ma |= (int(input().replace(".","0").replace("*","1"),2) << ((H-i-1)*W))
    flag = False
    hw = [[h,w] for h,w in product(range(H,0,-1),range(W,0,-1))]
    hw = sorted(hw,key=lambda x: -x[1]*x[0])
    ans = 0
    for h,w in hw:
        for i,j in product(range(H-h+1),range(W-w+1)):
            b = (sum([((2**w-1) << j) << k*W for k in range(h)]) ) << i*W
            c = ma&b
            if not c :flag = True; ans = max(ans,h*w); break
        else:
            continue
        if flag: break
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
while 1:
  h,w=map(int,raw_input().split())
  if h==w==0: break
  a=[0]*w
  F=[]
  for _ in [0]*h:
    b=raw_input()
    f=[0]*w
    for i in range(w):
      f[i]=[a[i]+1,0][b[i]=="*"]
    F.append(f)
    a=f

  s=0
  for i in range(h):
    f=F[i]
    for j in range(w):
      m=1e9
      for k in range(j+1,w+1):
        m=min(f[j:k])
        s=max(s,m*(k-j))
  print s

Submission status: Time Limit Exceeded

Solution code:
while 1:
  h,w=map(int,raw_input().split())
  if h==w==0: break
  W=range(w)
  a=[0]*w
  s=0
  for _ in [0]*h:
    b=raw_input()
    f=[0]*w
    for i in W:
      f[i]=[a[i]+1,0][b[i]=="*"]
      m=1e9
      for j in range(i+1):
        m=min(f[j:i+1])
        if m!=0: s=max(s,m*(i+1-j))
    a=f
  print s

Submission status: Time Limit Exceeded

Solution code:
while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  H = range(h)
  A = [0]*h
  for i in H:
    x = raw_input().replace(".", "1").replace("*", "0")
    A[i] = map(int, list(x))
  B = A[:]
  C = [0]*h
  for j in H[1:]:
    M = ["1","11","111"]
    for i in H[j:]:
      x = [e1 & e2 for e1, e2 in zip(B[i-j], A[i])]
#      B[i-j] = x
#      M.append(sorted("".join(map(str, x)).split("0"))[-1])
    C[j] = len(sorted(M)[-1])*(j+1)
  print max(C)

Submission status: Time Limit Exceeded

Solution code:
while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  H = range(h)
  A = [0]*h
  for i in H:
    x = raw_input().replace(".", "1").replace("*", "0")
    A[i] = map(int, list(x))
  B = A[:]
  C = [0]*h
  for j in H[1:]:
    M = ["1","11","111"]
    for i in H[j:]:
      x = [e1 & e2 for e1, e2 in zip(B[i-j], A[i])]
      B[i-j] = x[:]
#      M.append(sorted("".join(map(str, x)).split("0"))[-1])
    C[j] = len(sorted(M)[-1])*(j+1)
  print max(C)

Submission status: Time Limit Exceeded

Solution code:
while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  H = range(h)
  A = [0]*h
  for i in H:
    x = raw_input().replace(".", "1").replace("*", "0")
    A[i] = map(int, list(x))
  B = A[:]
  C = [0]*h
  for j in H[1:]:
    M = ["1","11","111"]
    for i in H[j:]:
      x = [e1 & e2 for e1, e2 in zip(B[i-j], A[i])]
      B[i-j] = x[:]
      x=sorted("".join(map(str, x)).split("0"))
#      M.append(x[-1])
    C[j] = len(sorted(M)[-1])*(j+1)
  print max(C)

Submission status: Time Limit Exceeded

Solution code:
while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  H = range(h)
  A = [0]*h
  for i in H:
    x = raw_input().replace(".", "1").replace("*", "0")
    A[i] = map(int, list(x))
  B = A[:]
  C = [0]*h
  for j in H[1:]:
    M = ["1","11","111"]
    for i in H[j:]:
      x = [e1 * e2 for e1, e2 in zip(B[i-j], A[i])]
      B[i-j] = x[:]
      x=sorted("".join(map(str, x)).split("0"))
#      M.append(x[-1])
    C[j] = len(sorted(M)[-1])*(j+1)
  print max(C)

Submission status: Time Limit Exceeded

Solution code:
def f(k,j): return max(M[k],j-C[k])
while 1:
  h,w = map(int, raw_input().split())
  if h==w==0: break
  H = range(h)
  C = [0]*(h+1)
  M = C[:]
  a=[0]*w
  for i in H:
    x = raw_input()
    b=[0]*w
    sp=-1
    C = [-1]*(h+1)
    for j in range(w):
      if x[j]=="*":
        c=0
      elif x[j]==".":
        c=a[j]+1
      b[j]=c
      if c>sp:
        C[sp+1:c+1]=[j]*(c-sp)
      elif c<sp:
        for k in range(c+1,sp+1):
          M[k]=f(k,j)
          C[k]=-1
      sp=c
    for k in range(1,sp+1):
      if C[k]>=0:
        M[k]=f(k,w)
    a=b
  s=max([a*b for a,b in zip(M, H+[h])])
  print s

Submission status: Time Limit Exceeded

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

import sys
import os
import math
import random

def print2d(M):
    print()
    for row in M:
        print(row)

for s in sys.stdin:
    H, W = map(int, s.split())
    if H == W == 0:
        break

    M = []
    for i in range(H):
        M.append(input().strip())
    #print2d(M)

    # make support map (H x W)
    S = [[0 for i in range(W)] for j in range(H)]
    for y in range(H-1, -1, -1):
        cnt = 0
        for x in range(W-1, -1, -1):
            if M[y][x] == '.':
                cnt += 1
            else:
                cnt = 0
            S[y][x] = cnt
    #print2d(S)

    max_area = 0
    for y in range(H):
        for x in range(W):
            if M[y][x] == '.':
                y_offset = 0
                min_width = S[y][x]
                while y + y_offset < H and M[y + y_offset][x] == '.':
                    if S[y + y_offset][x] < min_width:
                        min_width = S[y + y_offset][x]

                    area = min_width * (y_offset + 1)
                    if area > max_area:
                        max_area = area

                    y_offset += 1
    print(max_area)

Submission status: Time Limit Exceeded

Solution code:
import re
while True:
    H, W = map(int, input().split())
    if H == 0:
        break
    x = [input() for _ in range(H)]
    s = ''.join(x)
    maxv = 0
    for i, line in enumerate(x):
        for it in re.finditer('[.]+', line):
            a, b = it.start(0)+H*i, it.end(0)+H*i
            edge = s[a:b]
            j = 0
            while s[a:b] == edge:
                a += H
                b += H
                j += 1
            maxv = max(maxv, j*len(edge))
    print(maxv)

Submission status: Time Limit Exceeded

Solution code:
def dotHeight(y,x):
    cnt=0
    for i in range(y,-1,-1):
        if L[i][x]=="*":
            return cnt
        cnt+=1

def dotLength(y,x):
    cnt=0
    for i in range(x,-1,-1):
        if L[y][i]=="*":
            return cnt
        cnt+=1

while True:
    H,W=map(int,raw_input().split())
    if H==W==0:break
    L=[["*"]+list(raw_input())+["*"] for i in range(H)]
    L.append(["*"]*(W+2))
    L.insert(0,["*"]*(W+2))
    dp=[[set() for i in range(W+2)] for i in range(H+2)]
    maxInt=0
    for i in range(1,H+2):
        for j in range(1,W+2):
            if L[i][j]==".":
                if L[i-1][j]==L[i][j-1]=="*":
                    dp[i][j].add((1,1))
                    maxInt=max(maxInt,1)
                elif L[i-1][j]=="*":
                    for k in dp[i][j-1]:
                        dp[i][j].add((k[0]+1,1))
                        maxInt=max(maxInt,k[0]+1)
                elif L[i][j-1]=="*":
                    for k in dp[i-1][j]:
                        dp[i][j].add((1,k[1]+1))
                        maxInt=max(maxInt,k[1]+1)
                else:
                    h=dotHeight(i,j)
                    l=dotLength(i,j)
                    for k in dp[i][j-1]:
                        dp[i][j].add((k[0]+1,min(k[1],h)))
                        maxInt=max(maxInt,(k[0]+1)*min(k[1],h))
                    for k in dp[i-1][j]:
                        dp[i][j].add((min(k[0],l),k[1]+1))
                        maxInt=max(maxInt,min(k[0],l)*(k[1]+1))
        dp[i-1]=[]
    print maxInt

Submission status: Time Limit Exceeded

Solution code:
while True:
    H,W=map(int,raw_input().split())
    if H==W==0:break
    L=[["*"]+list(raw_input())+["*"] for i in range(H)]
    L.append(["*"]*(W+2))
    L.insert(0,["*"]*(W+2))
    dp=[[set() for i in range(W+2)] for i in range(H+2)]
    T=[[[0,0] for i in range(W+2)] for i in range(H+2)]
    for i in range(1,H+1):
        for j in range(1,W+1):
            if L[i][j]==".":
                T[i][j][0]+=T[i][j-1][0]+1
                T[i][j][1]+=T[i-1][j][1]+1
    maxInt=0
    for i in range(1,H+2):
        for j in range(1,W+2):
            if L[i][j]==".":
                if L[i-1][j]==L[i][j-1]=="*":
                    dp[i][j].add((1,1))
                    maxInt=max(maxInt,1)
                elif L[i-1][j]=="*":
                    for k in dp[i][j-1]:
                        dp[i][j].add((k[0]+1,1))
                        maxInt=max(maxInt,k[0]+1)
                elif L[i][j-1]=="*":
                    for k in dp[i-1][j]:
                        dp[i][j].add((1,k[1]+1))
                        maxInt=max(maxInt,k[1]+1)
                else:
                    h=T[i][j][1]
                    l=T[i][j][0]
                    for k in dp[i][j-1]:
                        m=min(k[1],h)
                        dp[i][j].add((k[0]+1,m))
                        maxInt=max(maxInt,(k[0]+1)*m)
                    for k in dp[i-1][j]:
                        m=min(k[0],l)
                        dp[i][j].add((m,k[1]+1))
                        maxInt=max(maxInt,m*(k[1]+1))
        dp[i-1]=[]
    print maxInt

Submission status: Time Limit Exceeded

Solution code:
while True:
    H,W = map(int, raw_input().split(" "))
    if (H,W) == (0,0):
        break
    field = [raw_input() for _ in xrange(H)]
    space = [[0]*(W+1) for _ in xrange(H)]
    for x in xrange(W-1,-1,-1):
        for y in xrange(H):
            if field[y][x]==".":
                space[y][x] = space[y][x+1]+1 
    ans = 0
    for x in xrange(W):
        for y in xrange(H):
            for h in xrange(y+1,H+1):
                ans = max(ans, min(s[x] for s in space[y:h])*(h-y))
    print ans

Submission status: Time Limit Exceeded

Solution code:
while True:
    H,W = map(int, raw_input().split(" "))
    if (H,W) == (0,0):
        break
    field = [raw_input() for _ in xrange(H)]
    space = [[0]*(W+1) for _ in xrange(H)]
    for x in xrange(W-1,-1,-1):
        for y in xrange(H):
            if field[y][x]==".":
                space[y][x] = space[y][x+1]+1 
    ans = 0
    for x in xrange(W):
        for y in (yy for yy in xrange(H) if field[y][x] == "."):
            for h in xrange(y+1,H+1):
                ans = max(ans, min(s[x] for s in space[y:h])*(h-y))
    print ans

Submission status: Time Limit Exceeded

Solution code:
def solve(field,H,W):
    space = [[0]*(W+1) for _ in xrange(H)]
    for x in xrange(W-1,-1,-1):
        for y in xrange(H):
            if field[y][x]==".":
                space[y][x] = space[y][x+1]+1 
    ans = 0
    for x in xrange(W):
        for y in (yy for yy in xrange(H) if field[y][x] == "."):
            for h in xrange(y+1,H+1):
                ans = max(ans, min(s[x] for s in space[y:h])*(h-y))
                if ans > (W-x)*(H-y):
                    return ans
    return ans

while True:
    H,W = map(int, raw_input().split(" "))
    if (H,W) == (0,0):
        break
    field = [raw_input() for _ in xrange(H)]
    print solve(field,H,W)

Submission status: Time Limit Exceeded

Solution code:
class Rect():
    
    def __init__(self, x_range, y_range):
        self.x_range = x_range
        self.y_range = y_range

    @property
    def w(self):
        return len(self.x_range)

    @property
    def h(self):
        return len(self.y_range)
        
    def __str__(self):
        return "Rect({},{})".format(str(self.x_range),str(self.y_range))

    def __contains__(self, pos):
        x,y = pos
        left,right = self.x_range[0],self.x_range[-1]
        buttom,top = self.y_range[0],self.y_range[-1]        
        return left<=x<=right and buttom<=y<=top

    def divide(self, pos):
        x,y = pos
        x_i = self.x_range.index(x)
        y_i = self.y_range.index(y)
        rects = [Rect(self.x_range[:x_i],self.y_range),
                 Rect(self.x_range[x_i+1:],self.y_range),
                 Rect(self.x_range,self.y_range[:y_i]),
                 Rect(self.x_range,self.y_range[y_i+1:])]        
        rem_list = [] #TEMP
        for r in rects:
            if r.x_range == [] or r.y_range == []:
                rem_list.append(r)

        for r in rem_list:
            rects.remove(r)

        return rects

def solveA(field,H,W):
    space = [[0]*(W+1) for _ in xrange(H)]
    for x in xrange(W-1,-1,-1):
        for y in xrange(H):
            if field[y][x]==".":
                space[y][x] = space[y][x+1]+1 
    ans = 0
    for x in xrange(W):
        for y in (yy for yy in xrange(H) if field[yy][x] == "."):
            mi = space[y][x]
            for h in xrange(y,H):
                if(field[h][x] == "*"):
                    break
                mi = min(mi, space[h][x])
                ans = max(ans, mi*(h-y+1))
    return ans

def solveB(field,H,W):
    rects = [Rect(range(W),range(H))]
    for x in xrange(W):
        for y in (yy for yy in xrange(H) if field[yy][x] == "*"):
            for r in filter(lambda rr:(x,y) in rr, rects):
                rects.extend(r.divide((x,y)))
                rects.remove(r)
    return max(r.w*r.h for r in rects)


while True:
    H,W = map(int, raw_input().split())
    if (H,W) == (0,0):
        break
    field = [raw_input() for _ in xrange(H)]
    count = sum(f.count("*") for f in field)
    if count > H*W/4:
        print solveA(field,H,W)
    else:
        print solveB(field,H,W)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def ge(H,W):
    q = deque([(0,0)])
    while q:
        x,y = q.popleft()
        yield (x,y)
        if y == 0 and x+1 < W:
            q.append([x+1,y])
        if y+1 < H:
            q.append([x,y+1])

def solve(field,H,W):
    space = [[0]*(W+1) for _ in xrange(H)]
    for x in xrange(W-1,-1,-1):
        for y in xrange(H):
            if field[y][x]==".":
                space[y][x] = space[y][x+1]+1 
    ans = 0
    x,y = 0,0
    for x,y in ((xx,yy) for xx,yy in ge(H,W) if field[yy][xx] == "."):
        mi = space[y][x]
        for h in xrange(y,H):
            if(field[h][x] == "*"):
                break
            mi = min(mi, space[h][x])
            ans = max(ans, mi*(h-y+1))
            if (W-x)*(H-y) < ans:
                return ans
    return ans

while True:
    H,W = map(int, raw_input().split())
    if (H,W) == (0,0):
        break
    field = [raw_input() for _ in xrange(H)]
    print solve(field,H,W)

Submission status: Time Limit Exceeded

Solution code:
def cut(squares):
    ret = []
    for s in squares:
        for i,r in enumerate(ret):
            if s[0] >= r[0] and s[1] >= r[1]:#replace
                ret[i] = s
                break
            if s[0] <= r[0] and s[1] <= r[1]:#remove
                break
        else:
            ret.append(s)#append
    return ret

def merge(left, buttom):
    ret = []
    for b in buttom:
        for l in left:
            w = min(b[0],l[0]+1)
            h = min(b[1]+1,l[1])
            ret+=[(w,h),(1,b[1]+1),(l[0]+1,1)]
    return ret

while True:
    H,W = map(int, raw_input().split())
    if (H,W) == (0,0):
        break
    field = [raw_input() for _ in xrange(H)]
    DP = [[[(0,0)] for _ in xrange(W+1)] for _ in xrange(H+1)]    
    for x in xrange(W-1,-1,-1):
        for y in (y for y in xrange(H-1,-1,-1) if field[y][x] != "*"):
            DP[y][x] = cut(merge(DP[y][x+1],DP[y+1][x]))
    ans = 0
    for x in xrange(W):
        for y in xrange(H):
            if DP[y][x]:
                ans = max(ans,max(w*h for w,h in DP[y][x]))
    print ans

Submission status: Time Limit Exceeded

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

def histgram(mass, h, w):
    table = [[0]*w for i in range(h)]
    for i in range(h):
        for j in range(w):
            if mass[i][j] == '*':
                table[i][j] = 0
            else:
                table[i][j] = table[i-1][j] + 1
    return table

def get_rectangle_area(table, w):
    maxv = 0
    for i in range(w):
        for j in range(i, w):
            minh = 1000000
            for k in range(i, j+1):
                minh = min(minh, table[k])
            maxv = max(maxv, minh*(j-i+1))
    return maxv

while True:
    h, w = map(int, raw_input().split())
    if h == w == 0:
        break
    mass = [raw_input() for i in range(h)]
    table = histgram(mass, h, w)
    ans = 0
    for tab in table:
        ans = max(ans, get_rectangle_area(tab, w))
    print ans

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
#http://www.checkio.org/mission/spaceship-landing-strip/ verifier.

def checkio(data):
	y=len(data)
	x=len(data[0])
	m=[[0]*x for i in range(y)]
	for j in range(y):
		r=0
		for i in range(x):
			if data[j][i]=='.': r+=1
			else: r=0
			m[j][i]=r
	r=0
	for i in range(x):
		for j in range(y):
			M=9999999
			for k in range(j,y):
				M=min(M,m[k][i])
				r=max(r,M*(k-j+1))
	return r

if __name__=='__main__':
	try:
		while True:
			y,x=[int(e) for e in raw_input().split()]
			if y==0: break
			data=[raw_input().rstrip() for i in range(y)]
			print(checkio(data))
	except EOFError:
		pass

Submission status: Time Limit Exceeded

Solution code:
while 1:
	H,W = map(int,raw_input().split())
	if H == 0: break
	A = [raw_input() for i in range(H)]
	S = [[0]*W for i in range(H)]
	L = ans = 0
	for h in range(H):
		for w in range(W):
			if A[h][w] == ".":
				L += 1
			else:
				L = 0
			S[h][w] = L
			if L > 0:
				a = L
				for hi in range(h-1,-1,-1):
					if S[hi][w] == 0:
						break
					a = min(a,S[hi][w])
					ans = max(ans,a*(h-hi+1))
	print ans

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/python
#http://www.checkio.org/mission/spaceship-landing-strip/ verifier.
#sadly TLE for aizu0116

import sys
if sys.version_info[0]>=3: raw_input=input

def checkio(data):
	y=len(data)
	x=len(data[0])
	m=[[0]*x for i in range(y)]
	for j in range(y):
		r=0
		for i in range(x):
			if data[j][i]=='.': r+=1
			#if data[j][i]==1: r+=1
			else: r=0
			m[j][i]=r
	r=0
	for i in range(x):
		for j in range(y):
			M=9999999
			for k in range(j,y):
				M=min(M,m[k][i])
				r=max(r,M*(k-j+1))
	return r

if __name__=='__main__':
	try:
		while True:
			y,x=[int(e) for e in raw_input().split()]
			if y==0: break
			data=[raw_input().rstrip() for i in range(y)]
			print(checkio(data))
	except EOFError:
		pass