Problem:
 Score : 400 points    Problem Statement There is a grid with H horizontal rows and W vertical columns, and there are obstacles on some of the squares.  Snuke is going to choose one of the squares not occupied by an obstacle and place a lamp on it.
The lamp placed on the square will emit straight beams of light in four cardinal directions: up, down, left, and right.
In each direction, the beam will continue traveling until it hits a square occupied by an obstacle or it hits the border of the grid. It will light all the squares on the way, including the square on which the lamp is placed, but not the square occupied by an obstacle.  Snuke wants to maximize the number of squares lighted by the lamp.  You are given H strings S_i ( 1 \leq i \leq H ), each of length W . If the j -th character ( 1 \leq j \leq W ) of S_i is # , there is an obstacle on the square at the i -th row from the top and the j -th column from the left; if that character is . , there is no obstacle on that square.  Find the maximum possible number of squares lighted by the lamp.      Constraints  1 \leq H \leq 2,000  1 \leq W \leq 2,000  S_i is a string of length W consisting of # and . .  . occurs at least once in one of the strings S_i ( 1 \leq i \leq H ).         Input Input is given from Standard Input in the following format:  H  W  S_1  :  S_H       Output Print the maximum possible number of squares lighted by the lamp.        Sample Input 1 4 6
#..#..
.....#
....#.
#.#...      Sample Output 1 8  If Snuke places the lamp on the square at the second row from the top and the second column from the left, it will light the following squares: the first through fifth squares from the left in the second row, and the first through fourth squares from the top in the second column, for a total of eight squares.       Sample Input 2 8 8
..#...#.
....#...
##......
..###..#
...#..#.
##....#.
#...#...
###.#..#      Sample Output 2 13

Solution (Python):
h, w = map(int,input().split())
grid = []
for i in range(h):
    grid.append(list(input()))
L = [[0 for i in range(w)] for j in range(h)]
R = [[0 for i in range(w)] for j in range(h)]
U = [[0 for i in range(w)] for j in range(h)]
D = [[0 for i in range(w)] for j in range(h)]

for i in range(w):
    if grid[0][i] == '
        U[0][i] = 0
    else:
        U[0][i] = 1
for i in range(1,h):
    for j in range(w):
        if grid[i][j] == '
            U[i][j] = 0
        else:
            U[i][j] = U[i-1][j] + 1
 
for i in range(w):
    if grid[-1][i] == '
        D[-1][i] = 0
    else:
        D[-1][i] = 1
for i in range(h-2, -1,-1):
    for j in range(w):
        if grid[i][j] == '
            D[i][j] = 0
        else:
            D[i][j] = D[i+1][j] + 1

for i in range(h):
    if grid[i][-1] == '
        R[i][-1] = 0
    else:
        R[i][-1] = 1
for i in range(h):
    for j in range(w-2,-1,-1):
        if grid[i][j] == '
            R[i][j] = 0
        else:
            R[i][j] = R[i][j+1] + 1

for i in range(h):
    if grid[i][0] == '
        L[i][0] = 0
    else:
        L[i][0] = 1
for i in range(h):
    for j in range(1,w):
        if grid[i][j] == '
            L[i][j] = 0
        else:
            L[i][j] = L[i][j-1] + 1
ans = 0
for i in range(h):
    for j in range(w):
        
        ans = max(ans, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)
print(ans)

Solution (Python):
h,w = map(int, input().split())
l = [None]*h
for i in range(h):
    l[i] = list(input())

cnt_h = [0]*w
cnt_w=0
ans=0
for i in range(h):
    for j in range(w):
        now = l[i][j]
        if now=="
            cnt_w=0
            cnt_h[j]=0
            continue

        if cnt_w==0:
            for k in range(j,w):
                if l[i][k] != "
                    cnt_w+=1
                else:
                    break
        if cnt_h[j] == 0:
            for x in range(i,h):
                if l[x][j] != "
                    cnt_h[j]+=1
                else:
                    break

        sm = cnt_w + cnt_h[j]
        if ans < sm:
            ans=sm
    cnt_w=0
print(ans-1)

Solution (Python):
import numpy as np

H,W = map(int, input().split())
S = []
for h in range(H):
  S.append(list(input()))
G = np.array(S)
G = np.where(G == ".", 1, 0)



L = np.zeros((H,W),dtype=int)
R = np.zeros((H,W),dtype=int)
U = np.zeros((H,W),dtype=int)
D = np.zeros((H,W),dtype=int)

for w in range(1,W):
  L[:,w] = (L[:,w-1]+1)*(G[:,w-1])
for w in range(W-1,0,-1):
  R[:,w-1] = (R[:,w]+1)*(G[:,w])
for h in range(1,H):
  U[h] = (U[h-1]+1)*(G[h-1])
for h in range(H-1,0,-1):
  D[h-1] = (D[h]+1)*(G[h])

ans = np.max((L+R+U+D)*G)+1
print(ans)

Solution (Python):
import numpy as np
h, w = map(int, input().split())
grid = np.array([list(input()) for _ in range(h)], dtype="str")

hgrid = np.zeros((h, w), dtype="int")

for hi in range(h):
    hdot = np.array(grid[hi] == ".", dtype="int")
    hgrid[hi] = hgrid[hi-1] * hdot + hdot
    
for hi in range(h-2, -1, -1):
    hi_1 = np.minimum(hgrid[hi+1], hgrid[hi] * hgrid[hi+1])
    hgrid[hi] = np.maximum(hgrid[hi], hi_1)
    
wgrid = np.zeros((h, w), dtype="int")

for wi in range(w):
    wdot = np.array(grid[:, wi] == ".", dtype="int")
    wgrid[:, wi] = wgrid[:, wi-1] * wdot + wdot
    
for wi in range(w-2, -1, -1):
    wi_1 = np.minimum(wgrid[:, wi+1], wgrid[:, wi] * wgrid[:, wi+1])
    wgrid[:, wi] = np.maximum(wgrid[:, wi], wi_1)

print(np.max(wgrid + hgrid) - 1)

Solution (Python):
import sys
import numpy as np 

h, w = map(int, sys.stdin.readline().split())
grid = np.array([list(sys.stdin.readline().rstrip()) for _ in range(h)], dtype='U')
grid = np.pad(grid, 1, mode='constant')

def main():
    cnt = np.zeros((h+2, w+2))
    cnt[grid == '.'] = np.inf
    
    l = cnt.copy()
    r = cnt.copy()
    u = cnt.copy()
    d = cnt.copy()

    for i in range(1, w+1):
        l[1:h+1, i] = np.minimum(l[1:h+1, i], l[1:h+1, i-1]+1)
        i = w + 1 - i
        r[1:h+1, i] = np.minimum(r[1:h+1, i], r[1:h+1, i+1]+1)
    
    for i in range(1, h+1):
        u[i, 1:w+1] = np.minimum(u[i, 1:w+1], u[i-1, 1:w+1]+1)
        i = h + 1 - i
        d[i, 1:w+1] = np.minimum(d[i, 1:w+1], d[i+1, 1:w+1]+1)
    
    res = np.maximum(l + r + u + d - 3, 0).astype(np.int64)
    return np.amax(res)

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
import os, sys, re, math, queue


def run_it():
	H,W = list(map(int,input().split(' ')))
	
	s_ary = []
	l_memo = [[0 for j in range(W)] for i in range(H)]
	r_memo = [[0 for j in range(W)] for i in range(H)]
	u_memo = [[0 for j in range(W)] for i in range(H)]
	b_memo = [[0 for j in range(W)] for i in range(H)]
	
	for _ in range(H):
		s_ary.append(input())
	
	for h in range(H):
		for w in range(W):
			if s_ary[h][w] == '.':
				if w == 0:	
					l_memo[h][w] = 1
				elif w > 0:
					l_memo[h][w] = l_memo[h][w-1] + 1
				if h == 0:
					u_memo[h][w] = 1
				elif h > 0:
					u_memo[h][w] = u_memo[h-1][w] + 1
			
			if s_ary[-h-1][-w-1] == '.':
				if w == 0:
					r_memo[-h-1][-w-1] = 1
				elif w > 0:
					r_memo[-h-1][-w-1] = r_memo[-h-1][-w] + 1	
				if h == 0:
					b_memo[-h-1][-w-1] = 1
				elif h > 0:
					b_memo[-h-1][-w-1] = b_memo[-h][-w-1] + 1
	
	ret = 0
	for h in range(H):
		for w in range(W):
			tmp = l_memo[h][w] + r_memo[h][w] + u_memo[h][w] + b_memo[h][w] - 3
			ret = max(ret, tmp)
	
	print(ret)
				
if sys.platform == 'ios':
	for i in range(2):
		sys.stdin = open('Dtest' + str(i) + '.txt')
		run_it()
else:
	run_it()

Solution (Python):
h, w = list(map(int, input().split(' ')))
field = []
for i in range(h):
    field.append(input())
 
dp = []
for i in range(h):
    dp.append([(0, 0)] * w)
for i in range(h):
    for j in range(w):  
        if field[i][j] == '
            x, y = 0, 0
        else:
            if i == j == 0:
               x, y = 1, 1
            else:
                y = (dp[i-1][j][0] + 1) if i-1 >= 0 else 1
                x = (dp[i][j-1][1] + 1) if j-1 >= 0 else 1
        dp[i][j] = (y, x)
ans = 0 if field[0][0] == '
 
for i in range(h-1, -1, -1):
    for j in range(w-1, -1, -1):
        if field[i][j] != '
            y = dp[i+1][j][0] if i+1 < h else dp[i][j][0]
            x = dp[i][j+1][1] if j+1 < w else dp[i][j][1]
            dp[i][j] = (max(dp[i][j][0], y), max(dp[i][j][1], x))
        ans = max(dp[i][j][0] + dp[i][j][1] - 1, ans)
print(ans)

Solution (Python):
h, w = map(int, input().split())
s = [input() for _ in range(h)]
sy = [0] * w
ret = 0
for y in range(h):
    seqx = 0
    seqy = 0
    for x in range(w):
        if s[y][x] == '.':
            if sy[x] == 0:
                yy = y
                while yy < h and s[yy][x] != '
                    yy += 1
                sy[x] = yy - y
            seqx += 1
            seqy = max(seqy, sy[x])
            ret = max(ret, seqx + seqy - 1)
        else:
            seqx = 0
            seqy = 0
            sy[x] = 0
print(ret)

Solution (Python):
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
SH = []
SW = []

for h in range(H):
    SW.append([])
    c = 0
    for w in range(W):
        if S[h][w] == '
            if c != 0:
                for _ in range(c):
                    SW[h].append(c)
            SW[h].append(0)
            c = 0
        else:
            c += 1
    for _ in range(c):
        SW[h].append(c)

for w in range(W):
    SH.append([])
    c = 0
    for h in range(H):
        if S[h][w] == '
            if c != 0:
                for _ in range(c):
                    SH[w].append(c)
            SH[w].append(0)
            c = 0
        else:
            c += 1
    for _ in range(c):
        SH[w].append(c)

ans = -1
for h in range(H):
    for w in range(W):
        ans = max(ans, SW[h][w] + SH[w][h] - 1)

print(ans)

Solution (Python):
h, w = map(int, input().split())
s = [input() for _ in range(h)]

l = [[0] * w for _ in range(h)]
r = [[0] * w for _ in range(h)]
u = [[0] * w for _ in range(h)]
d = [[0] * w for _ in range(h)]

for i in range(h):
  for j in range(w):
    if s[i][j] == '.':
      if j == 0:
        l[i][j] = 1
      else:
        l[i][j] = l[i][j-1] + 1
    if s[i][w-j-1] == '.':
      if j == 0:
        r[i][w-j-1] = 1
      else:
        r[i][w-j-1] = r[i][w-j] + 1

for j in range(w):
  for i in range(h):
    if s[i][j] == '.':
      if i == 0:
        u[i][j] = 1
      else:
        u[i][j] = u[i-1][j] + 1
    if s[h-i-1][j] == '.':
      if i == 0:
        d[h-i-1][j] = 1
      else:
        d[h-i-1][j] = d[h-i][j] + 1

maximum = 1
for i in range(h):
  for j in range(w):
    maximum = max(maximum, l[i][j] + r[i][j] + u[i][j] + d[i][j] - 3)
print(maximum)

Solution (Python):
import sys
input = sys.stdin.readline


def main():
    H, W = map(int, input().split())
    s = [list(input()) for _ in range(H)]
    L = [[0] * W for _ in range(H)]
    R = [[0] * W for _ in range(H)]
    T = [[0] * W for _ in range(H)]
    B = [[0] * W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if s[h][w] == "
                R[h][w] = 0
            elif w == 0:
                R[h][w] = 1
            else:
                R[h][w] = R[h][w - 1] + 1
    for h in range(H):
        for w in reversed(range(W)):
            if s[h][w] == "
                L[h][w] = 0
            elif w == W - 1:
                L[h][w] = 1
            else:
                L[h][w] = L[h][w + 1] + 1
    for w in range(W):
        for h in range(H):
            if s[h][w] == "
                B[h][w] = 0
            elif h == 0:
                B[h][w] = 1
            else:
                B[h][w] = B[h-1][w] + 1
    for w in range(W):
        for h in reversed(range(H)):
            if s[h][w] == "
                T[h][w] = 0
            elif h == H - 1:
                T[h][w] = 1
            else:
                T[h][w] = T[h + 1][w] + 1
    ans = 0
    for h in range(H):
        for w in range(W):
            res = R[h][w] + L[h][w] + B[h][w] + T[h][w] - 3
            ans = max(ans, res)
    print(int(ans))


if __name__ == "__main__":
    main()

Solution (Python):
def main():
    H,W = map(int,input().split())
    S = [[1 if s == "." else 0 for s in input()] for _ in range(H)]

    if H == 1:
        for w in range(1,W):
            if S[0][w] and S[0][w - 1]:
                S[0][w] += S[0][w - 1]
        print(max(S[0]))
        return
    if W == 1:
        ans = 0
        for h in range(1,H):
            if S[h][0] and S[h-1][0]:
                S[h][0] += S[h - 1][0]
                ans = max(ans,S[h][0])
        print(ans)
        return


    R = [[0]*W for _ in range(H)]
    L = [[0]*W for _ in range(H)]
    D = [[0]*W for _ in range(H)]
    U = [[0]*W for _ in range(H)]

    for h in range(H):
        for w in range(1,W - 1):
            if S[h][w] and S[h][w - 1]:
                L[h][w] += L[h][w - 1] + 1
            if S[h][W - w] and S[h][W - w - 1]:
                R[h][W - w - 1] += R[h][W - w] + 1
        if S[h][W -1] and S[h][W - 2]:
            L[h][W - 1] += L[h][W - 2] + 1
        if S[h][0] and S[h][1]:
            R[h][0] += R[h][1] + 1
    for w in range(W):
        for h in range(1,H-1):
            if S[h-1][w] and S[h][w]:
                U[h][w] += U[h-1][w] + 1
            if S[H - h][w] and S[H - h - 1][w]:
                D[H - h - 1][w] += D[H - h][w] + 1
        if S[H - 1][w] and S[H - 2][w]:
            D[H - 1][w] += D[H-2][w] + 1
        if S[0][w] and S[1][w]:
            U[0][w] += U[1][w] + 1
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans,U[h][w] + D[h][w] + R[h][w] + L[h][w])
    print(ans + 1)
    return 

if __name__ == "__main__":
    main()

Solution (Python):
def main():
    NEG = -10**6
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    T = [[NEG] * W for _ in range(H)]
    for w in range(W):
        b = NEG
        for h in range(H):
            if S[h][w] == '.':
                if b == NEG:
                    b = h
            else:
                if b != NEG:
                    for j in range(b, h):
                        T[j][w] = h - b
                    b = NEG
        if b != NEG:
            for j in range(b, h + 1):
                T[j][w] = h + 1 - b
    m = 0
    for s, t in zip(S, T):
        b = NEG
        for i in range(len(s)):
            if s[i] == '
                if b != NEG:
                    m = max(m, i - b - 1 + max(t[b:i]))
                    b = NEG
            else:
                if b == NEG:
                    b = i
        if b != NEG:
            m = max(m, i - b + max(t[b:i + 1]))
    print(m)

main()

Solution (Python):

H, W = map(int, input().split())
S = ["

LEFT = [[0 for j in range(W+2)] for i in range(H+2)]
RIGHT = [[0 for j in range(W+2)] for i in range(H+2)]
UP = [[0 for j in range(W+2)] for i in range(H+2)]
DOWN = [[0 for j in range(W+2)] for i in range(H+2)]

for h in range(H+2):
  for w in range(W+2):
    if S[h][w] == ".":
      LEFT[h][w] = LEFT[h][w-1] + 1
    else:
      LEFT[h][w] = 0

for h in range(H+2):
  for w in range(W+2)[::-1]:
    if S[h][w] == ".":
      RIGHT[h][w] = RIGHT[h][w+1] + 1
    else:
      RIGHT[h][w] = 0

for h in range(H+2)[::-1]:
  for w in range(W+2):
    if S[h][w] == ".":
      UP[h][w] = UP[h+1][w] + 1
    else:
      UP[h][w] = 0

for h in range(H+2):
  for w in range(W+2):
    if S[h][w] == ".":
      DOWN[h][w] = DOWN[h-1][w] + 1
    else:
      DOWN[h][w] = 0

ans = -1

for h in range(H+2):
  for w in range(W+2):
    value = RIGHT[h][w] + LEFT[h][w] + UP[h][w] + DOWN[h][w] - 3
    ans = max(ans, value)

print(ans)

Solution (Python):
h, w = map(int, input().split())
grid = []
for i in range(h):
  gridi = input()
  grid.append(gridi)
xcnt = [[0]*w for i in range(h)]
ycnt = [[0]*w for i in range(h)]
ans = -10**9

for y in range(h):
  cnt = 0
  for x in range(w-1):
    if grid[y][x] == "
      cnt = 0
      continue
    if grid[y][x+1] == "
      xcnt[y][x] = cnt + 1
      cnt = 0
    else:
      cnt += 1
  if grid[y][w-1] == ".":
    xcnt[y][w-1] = cnt + 1

for y in range(h):
  for x in range(w-1):
    if grid[y][w-1-x] == "
      continue
    if grid[y][w-1-x-1] == ".":
      xcnt[y][w-1-x-1] = xcnt[y][w-1-x]


for x in range(w):
  cnt = 0
  for y in range(h-1):
    if grid[y][x] == "
      cnt = 0
      continue
    if grid[y+1][x] == "
      ycnt[y][x] = cnt + 1
      cnt = 0
    else:
      cnt += 1
  if grid[h-1][x] == ".":
    ycnt[h-1][x] = cnt + 1

for x in range(w):
  for y in range(h-1):
    if grid[h-1-y][x] == "
      continue
    if grid[h-1-y-1][x] == ".":
      ycnt[h-1-y-1][x] = ycnt[h-1-y][x]

for y in range(h):
  for x in range(w):
    ans = max(ans, xcnt[y][x] + ycnt[y][x] - 1)
print(ans)

Solution (Python):
h,w=map(int,input().split())
s=[input() for i in range(h)]
l=[[0]*w for i in range(h)]
r=[[0]*w for i in range(h)]
u=[[0]*w for i in range(h)]
d=[[0]*w for i in range(h)]
for i in range(h):
  if s[i][0]=='.':
    l[i][0]=1
  if s[i][w-1]=='.':
    r[i][w-1]=1
for i in range(w):
  if s[0][i]=='.':
    u[0][i]=1
  if s[h-1][i]=='.':
    d[h-1][i]=1
for i in range(h):
  for j in range(w):
    if j>=1:
      if s[i][j]=='.':
        l[i][j]=l[i][j-1]+1
    if j<w-1:
      if s[i][w-j-2]=='.':
        r[i][w-j-2]=r[i][w-j-1]+1
    if i>=1:
      if s[i][j]=='.':
        u[i][j]=u[i-1][j]+1
    if i<h-1:
      if s[h-i-2][j]=='.':
        d[h-i-2][j]=d[h-i-1][j]+1
ans=0
for i in range(h):
  for j in range(w):
    ans=max(ans,l[i][j]+r[i][j]+u[i][j]+d[i][j]-3)
print(ans)

Solution (Python):
H, W=map(int, input().split())
S=[]
S.append("".join(["
S.extend(["
S.append("".join(["
co1=[[0 for _ in range(W+2)] for _ in range(H+2)]
co2=[[0 for _ in range(W+2)] for _ in range(H+2)]

for i in range(1, H+2):
    ppos=0
    for j in range(W+2):
        if S[i][j]=="
            if S[i][j-1]==".":
                for k in range(ppos, j):
                    co1[i][k]=j-ppos
            ppos=j+1

for j in range(1, W+2):
    ppos=0
    for i in range(H+2):
        if S[i][j]=="
            if S[i-1][j]==".":
                for k in range(ppos, i):
                    co2[k][j]=i-ppos
            ppos=i+1

ans=0
for i in range(1, H+2):
    for j in range(1, W+2):
        ans=max(ans, co1[i][j]+co2[i][j]-1)
print(ans)

Solution (Python):
def calculate(h, w, arr):
    L = [[0]*w for i in range(h)]
    U = [[0]*w for i in range(h)]
    D = [[0]*w for i in range(h)]
    R = [[0]*w for i in range(h)]

    for ih in range(h):
        for iw in range(w):
            if ih == 0:
                U[ih][iw] = 1
            if iw == 0:
                L[ih][iw] = 1

            if arr[ih][iw] == 1:
                L[ih][iw] = 0
                U[ih][iw] = 0

            else:
                if iw > 0:
                    L[ih][iw] = L[ih][iw - 1] + 1
                if ih > 0:
                    U[ih][iw] = U[ih - 1][iw] + 1

            rih = h - 1 - ih
            riw = w - 1 - iw

            if rih == h - 1:
                D[rih][riw] = 1
            if riw == w - 1:
                R[rih][riw] = 1

            if arr[rih][riw] == 1:
                D[rih][riw] = 0
                R[rih][riw] = 0
            else:
                if riw < w - 1:
                    R[rih][riw] = R[rih][riw + 1] + 1
                if rih < h - 1:
                    D[rih][riw] = D[rih + 1][riw] + 1

    max = 0
    for ih in range(h):
        for iw in range(w):
            value = L[ih][iw] + R[ih][iw] + U[ih][iw] + D[ih][iw] - 3
            if value > max:
                max = value
    print(int(max))


S = input().split(" ")
H = int(S[0])
W = int(S[1])

arr = []
for i in range(H):
    q = input()
    tmp = []
    for qs in q:
        if qs == "
            tmp.append(1)
        if qs == ".":
            tmp.append(0)
    arr.append(tmp)

calculate(H, W, arr)

Solution (Python):
H, W = [int(a) for a in input().split()]
S = [None] * H
for i in range(H):
    S[i] = input()

L = [[0 for _ in range(W)] for _ in range(H)]
R = [[0 for _ in range(W)] for _ in range(H)]
U = [[0 for _ in range(W)] for _ in range(H)]
D = [[0 for _ in range(W)] for _ in range(H)]

ans = 0

for i in range(H):
    for j in range(W):
        
        if S[i][j] == '
        elif i == 0:        U[i][j] = 1
        else:               U[i][j] = U[i - 1][j] + 1

        
        if S[i][j] == '
        elif j == 0:  L[i][j] = 1
        else:       L[i][j] = L[i][j - 1] + 1

        
        if S[H - 1 - i][j] == '
        elif i == 0:    D[H - 1 - i][j] = 1
        else:           D[H - 1 - i][j] = D[H - i][j] + 1

        
        if S[i][W - 1 - j] == '
        elif j == 0:    R[i][W - 1 - j] = 1
        else:           R[i][W - 1 - j] = R[i][W - j] + 1

for i in range(H):
    for j in range(W):
        ans = max(ans, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)

print(ans)

Solution (Python):
H, W = [int(a) for a in input().split()]
S = [None] * H
for i in range(H):
    S[i] = input()

L = [[0 for _ in range(W)] for _ in range(H)]
R = [[0 for _ in range(W)] for _ in range(H)]
U = [[0 for _ in range(W)] for _ in range(H)]
D = [[0 for _ in range(W)] for _ in range(H)]

ans = 0


for i in range(H):
    for j in range(W):

        if S[i][j] == '
            pass  
        else:
            
            if i == 0:  U[i][j] = 1
            else:       U[i][j] = U[i - 1][j] + 1

            
            if j == 0:  L[i][j] = 1
            else:       L[i][j] = L[i][j - 1] + 1

        
        if S[i][W - 1 - j] == '
            pass
        elif j == 0:
            R[i][W - 1 - j] = 1
        else:
            R[i][W - 1 - j] = R[i][W - j] + 1


for i in range(H - 1, -1, -1):
    for j in range(W):
        if S[i][j] == '
        elif i == H - 1:    D[i][j] = 1
        else:               D[i][j] = D[i + 1][j] + 1
        ans = max(ans, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)

print(ans)

Solution (Python):
import re

H,W = map(int,input().split())
arr = []

for i in range(H):
  S = list(map(int,input().replace("
  arr.append(S)

ANS = [[] for _ in range(H)]
for i in range(H):
  for j in range(W):
    if j == 0:
      ans = arr[i][j]
    elif arr[i][j-1] == 0:
      ans = arr[i][j]
    else:
      ans = ans + 1
    ANS[i].append(ans)

for i in range(H):
  for j in range(W):
    if j == 0:
      ans = arr[i][W-1-j]
    elif arr[i][W-j] == 0:
      ans = arr[i][W-1-j]
    else:
      ans = ans + 1
    ANS[i][W-1-j] += ans

for j in range(W):
  for i in range(H):
    if i == 0:
      ans = arr[i][j]
    elif arr[i-1][j] == 0:
      ans = arr[i][j]
    else:
      ans = ans + 1
    ANS[i][j] += ans

for j in range(W):
  for i in range(H):
    if i == 0:
      ans = arr[H-1-i][j]
    elif arr[H-i][j] == 0:
      ans = arr[H-1-i][j]
    else:
      ans = ans + 1
    ANS[H-1-i][j] += ans

    
    
ans = []
for j in range(W):
  for i in range(H):
    if arr[i][j] != 0:
      a = ANS[i][j] - 3
      ans.append(a)
print(int(max(ans)))

Solution (Python):
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
l = [[0] * W for _ in range(H)]
r = [[0] * W for _ in range(H)]
u = [[0] * W for _ in range(H)]
d = [[0] * W for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] != '
            if j != 0:
                r[i][j] = r[i][j - 1] + 1
            else:
                r[i][j] = 1

for i in range(H):
    for j in reversed(range(W)):
        if S[i][j] != '
            if j != W - 1:
                l[i][j] = l[i][j + 1] + 1
            else:
                l[i][j] = 1

for i in range(W):
    for j in range(H):
        if S[j][i] != '
            if j != 0:
                d[j][i] = d[j - 1][i] + 1
            else:
                d[j][i] = 1

for i in range(W):
    for j in reversed(range(H)):
        if S[j][i] != '
            if j != H - 1:
                u[j][i] = u[j + 1][i] + 1
            else:
                u[j][i] = 1

for i in range(H):
    for j in range(W):
        tmp = l[i][j] + r[i][j] + u[i][j] + d[i][j] - 3
        ans = max(ans, tmp)

print(ans)

Solution (Python):
H,W = list(map(int,input().split()))

S = [input() for i in range(H)]

L,R,U,D = [[[0]*W for i in range(H)] for i in range(4)]

for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            if i != 0:
                U[i][j] = U[i-1][j]+1
            else:
                U[i][j] = 1
            if j != 0:
                L[i][j] = L[i][j-1]+1
            else:
                L[i][j] = 1
            
        else:
            U[i][j] = 0
            L[i][j] = 0

        ri = H-i-1
        rj = W-j-1
        if S[ri][rj] == ".":
            if i != 0:
                D[ri][rj] = D[ri+1][rj]+1
            else:
                D[ri][rj] = 1
            if j != 0:
                R[ri][rj] = R[ri][rj+1]+1
            else:
                R[ri][rj] = 1
        else:
            D[ri][rj] = 0
            R[ri][rj] = 0


ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans,L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)

print(ans)

Solution (Python):
import sys
inputs = sys.stdin.readlines()

h, w = map(int, inputs[0].split())
S = [list(map(lambda x: 0 if x=='

w_costs = [[0]*w for _ in range(h)]
h_costs = [[0]*w for _ in range(h)]

def row_search(x, y):
    x_, cost = x, 0
    while x+1 < w and S[y][x+1]:
        x += 1
        cost += 1
    while x_ <= x:
        w_costs[y][x] = cost
        x -= 1
def col_search(x, y):
    y_, cost = y, 0
    while y+1 < h and S[y+1][x]:
        y += 1
        cost += 1
    while y_ <= y:
        h_costs[y][x] = cost
        y -= 1

for y in range(h):
    for x in range(w):
        if S[y][x]:
            if w_costs[y][x] == 0:
                row_search(x, y)
            if h_costs[y][x] == 0:
                col_search(x, y)

ans = 0
for y in range(h):
    for x in range(w):
        ans = max(ans, w_costs[y][x] + h_costs[y][x] + 1)
print(ans)

Solution (Python):
H,W=map(int,input().split())
S = []
for _ in range(H):
  S.append(list(input()))
  
Left = [[0] * W for i in range(H)]
for i in range(H):
  cur=0
  for j in range(W):
    
    if S[i][j]=='
      cur=0
    else:
      cur=cur+1
    Left[i][j]=cur
    
Right=[[0] * W for i in range(H)]
for i in range(H):
  cur=0
  for j in range(W-1,-1,-1):
    if S[i][j]=='
      cur=0
    else:
      cur+=1
      Right[i][j]=cur
      
Up=[[0] * W for i in range(H)]
for j in range(W):
  cur=0
  for i in range(H):
    if S[i][j]=='
      cur=0
    else:
      cur+=1
      Up[i][j]=cur
      
Down=[[0] * W for i in range(H)]
for j in range(W):
  cur=0
  for i in range(H-1,-1,-1):
    if S[i][j]=='
      cur=0
    else:
      cur+=1
      Down[i][j]=cur
      
res=0
for i in range(H):
  for j in range(W):
    if S[i][j]=='
      continue
    res=max(res,Left[i][j]+Right[i][j]+Up[i][j]+Down[i][j]-3)
print(res)

Solution (Python):
import numpy as np
H,W = map(int,input().split())
S=np.array([list(input().rstrip("\n")) for _ in range(H)]) == '.'
D = np.zeros((H,W),dtype=int)
U = np.zeros((H,W),dtype=int)
L = np.zeros((H,W),dtype=int)
R = np.zeros((H,W),dtype=int)
for i in range(H):
  U[i] = (U[i-1] + 1) * S[i]
  D[-i-1] = (D[-i] + 1) * S[-i-1]
for i in range(W):
  L[:,i] = (L[:,i-1] + 1) * S[:,i]
  R[:,-i-1] = (R[:,-i] + 1) * S[:,-i-1]
print(np.max(U+D+L+R)-3)

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    H, W = MAP()
    S = [input() for i in range(H)]
    
    L = [[0] * W for i in range(H)]
    R = [[0] * W for i in range(H)]
    D = [[0] * W for i in range(H)]
    U = [[0] * W for i in range(H)]
    
    for i in range(H):
        for j in range(W):
            if S[i][j] == "
                L[i][j] = 0
            elif j == 0:
                L[i][j] = 1
            else:
                L[i][j] = L[i][j-1] + 1
            
    for i in range(H):
        for j in range(W-1, -1, -1):
            if S[i][j] == "
                R[i][j] = 0
            elif j == W-1:
                R[i][j] = 1
            else:
                R[i][j] = R[i][j+1] + 1
    
    for i in range(H):
        for j in range(W):
            if S[i][j] == "
                U[i][j] = 0
            elif i == 0:
                U[i][j] = 1
            else:
                U[i][j] = U[i-1][j] + 1

    for i in range(H-1, -1, -1):
        for j in range(W):
            if S[i][j] == "
                D[i][j] = 0
            elif i == H-1:
                D[i][j] = 1
            else:
                D[i][j] = D[i+1][j] + 1
    ans = 0
    for i in range(H):
        for j in range(W):
            ans = max(ans, L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3)
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):

h,w=map(int,input().split())
g=[input() for i in range(h)]
l=[[0]*w for i in range(h)]
r=[[0]*w for i in range(h)]
u=[[0]*w for i in range(h)]
o=[[0]*w for i in range(h)]

for i in range(h):
    if g[i][0]=='.':
        l[i][0]=1

for i in range(h):
    for j in range(w-1):
        if g[i][j+1]=='.':
            l[i][j+1]=l[i][j]+1
        elif g[i][j+1]=='
            l[i][j+1]=0

for i in range(h):
    if g[i][w-1]=='.':
        r[i][w-1]=1

for i in range(h):
    for j in range(w-1,0,-1):
        if g[i][j-1]=='.':
            r[i][j-1]=r[i][j]+1
        elif g[i][j-1]=='
            r[i][j-1]=0

for i in range(w):
    if g[0][i]=='.':
        u[0][i]=1

for i in range(w):
    for j in range(h-1):
        if g[j+1][i]=='.':
            u[j+1][i]=u[j][i]+1
        elif g[j+1][i]=='
            u[j+1][i]=0

for i in range(w):
    if g[h-1][i]=='.':
        o[h-1][i]=1

for i in range(w):
    for j in range(h-1,0,-1):
        if g[j-1][i]=='.':
            o[j-1][i]=o[j][i]+1
        elif g[j-1][i]=='
            o[j-1][i]=0

ans=0
for i in range(h):
    for j in range(w):
        ans=max(ans,l[i][j]+r[i][j]+u[i][j]+o[i][j]-3)

print(ans)

Solution (Python):
import numpy as np

H, W = map(int, input().split())
G = []
for _ in range(H):
    G.append([1 if x == '.' else 0 for x in input()])
G = np.array(G)

North = np.cumsum(np.ones_like(G), axis=0)
North *= (1 - G)
North = np.maximum.accumulate(North, axis=0) * G

South = np.cumsum(np.ones_like(G), axis=0)
South *= np.flipud(1 - G)
South = np.maximum.accumulate(South, axis=0)
South = (H - np.flipud(South)) * G

West = np.cumsum(np.ones_like(G), axis=1)
West *= (1 - G)
West = np.maximum.accumulate(West, axis=1) * G

East = np.cumsum(np.ones_like(G), axis=1)
East *= np.fliplr(1 - G)
East = np.maximum.accumulate(East, axis=1)
East = (W - np.fliplr(East)) * G

print(np.amax(South - North + East - West) - 1)

Solution (Python):
import numpy as np

H, W = map(int, input().split())
G = []
for _ in range(H):
    G.append([1 if x == '.' else 0 for x in input()])
G = np.array(G)
HWOnes = np.ones_like(G)

North = np.cumsum(np.ones_like(G), axis=0)
North *= (1 - G)
North = np.maximum.accumulate(North, axis=0) * G

South = np.cumsum(np.ones_like(G), axis=0)
South *= np.flipud(1 - G)
South = np.maximum.accumulate(South, axis=0)
South = (H - np.flipud(South)) * G

West = np.cumsum(np.ones_like(G), axis=1)
West *= (1 - G)
West = np.maximum.accumulate(West, axis=1) * G

East = np.cumsum(np.ones_like(G), axis=1)
East *= np.fliplr(1 - G)
East = np.maximum.accumulate(East, axis=1)
East = (W - np.fliplr(East)) * G

print(np.amax(South - North + East - West - 1))