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):

w,h=map(int,input().split())
s=[input() for i in range(w)]
t=[[[],[]] for j in range(w)]
for i in range(w):
    k=0
    for j in range(h):
        if s[i][j]==".":
            k+=1
        else:
            t[i][0]+=[k for _ in range(k)]+[0]
            k=0
    t[i][0]+=[k for _ in range(k)]
for i in range(h):
    k=0
    for j in range(w):
        if s[j][i]==".":
            k+=1
        else:
            for l in range(1,k+1):
                t[j-l][1]+=[k]
            t[j][1]+=[0]
            k=0
    for l in range(1,k+1):
        t[w-l][1]+=[k]
answer=0
for i in range(w):
    for j in range(h):
        answer=max(t[i][0][j]+t[i][1][j],answer)
print(answer-1)

Solution (Python):
def slove():
    import sys
    input = sys.stdin.readline
    h, w = list(map(int, input().rstrip('\n').split()))
    s = [list(str(input().rstrip('\n'))) for _ in range(h)]

    U = [[0] * w for _ in range(h)]
    D = [[0] * w for _ in range(h)]
    R = [[0] * w for _ in range(h)]
    L = [[0] * w for _ in range(h)]

    b = True
    for i in range(h):
        for j in range(w):
            if b:
                U[i][j] = 1 if s[i][j] != "
                D[-i - 1][j] = 1 if s[-i - 1][j] != "
                R[i][-j - 1] = 1 if s[i][-j - 1] != "
                L[i][j] = 1 if s[i][j] != "
                b = False
            else:
                U[i][j] = 1 + U[i-1][j] if s[i][j] != "
                D[-i-1][j] = 1 + D[-i][j] if s[-i-1][j] != "
                R[i][-j-1] = 1 + R[i][-j] if s[i][-j-1] != "
                L[i][j] = 1 + L[i][j-1] if s[i][j] != "
    mt = 0
    for i in range(h):
        for j in range(w):
            mt = max(mt, U[i][j] + D[i][j] + R[i][j] + L[i][j] - 3)
    print(mt)


if __name__ == '__main__':
    slove()

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

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

h, w = li()
grid = [lc() for _ in range(h)]


left = [[0]*w for _ in range(h)]
for row in range(h):
    cur = 0
    for col in range(w-1, -1, -1):
        if grid[row][col] == ".":
            cur += 1
            left[row][col] = cur
        else:
            cur = 0


right = [[0]*w for _ in range(h)]
for row in range(h):
    cur = 0
    for col in range(w):
        if grid[row][col] == ".":
            cur += 1
            right[row][col] = cur
        else:
            cur = 0


up = [[0]*w for _ in range(h)]
for col in range(w):
    cur = 0
    for row in range(h-1, -1, -1):
        if grid[row][col] == ".":
            cur += 1
            up[row][col] = cur
        else:
            cur = 0


down = [[0]*w for _ in range(h)]
for col in range(w):
    cur = 0
    for row in range(h):
        if grid[row][col] == ".":
            cur += 1
            down[row][col] = cur
        else:
            cur = 0


ans = 0
for row in range(h):
    for col in range(w):
        ans = max(ans, left[row][col] + right[row][col] + up[row][col] + down[row][col])

print(ans-3)

Solution (Python):
t,*grid = open(0)
h,w = map(int,t.split())
L,R,U,D = eval("[[0]*(w+2) for _ in range(h+2)],"*4)
for y in range(h):
	for x in range(w):
		if grid[y][x]==".":
			L[y+1][x+1] = L[y+1][x]+1
		if grid[y][w-x-1]==".":
			R[y+1][w-x] = R[y+1][w-x+1]+1
for x in range(w):
	for y in range(h):
		if grid[y][x]==".":
			U[y+1][x+1] = U[y][x+1]+1
		if grid[h-y-1][x]==".":
			D[h-y][x+1] = D[h-y+1][x+1]+1
print(max(L[y][x] + R[y][x] + U[y][x] + D[y][x] -3 for y in range(1,h+1) for x in range(1,w+1)))

Solution (Python):
t,*l=open(0)
h,w=map(int,t.split())
grid = [[c=="."for c in C]for C in l]
L,R,U,D = eval("[[0]*(w+2) for _ in range(h+2)],"*4)
for y in range(h):
	for x in range(w):
		L[y+1][x+1] = (L[y+1][x]+1)*grid[y][x]
		R[y+1][w-x] = (R[y+1][w-x+1]+1)*grid[y][w-x-1]
for x in range(w):
	for y in range(h):
		U[y+1][x+1] = (U[y][x+1]+1)*grid[y][x]
		D[h-y][x+1] = (D[h-y+1][x+1]+1)*grid[h-y-1][x]
print(max(L[y][x] + R[y][x] + U[y][x] + D[y][x] -3 for y in range(1,h+1) for x in range(1,w+1)))

Solution (Python):
h,w = map(int,input().split())
grid = [[c=="."for c in input()]for _ in range(h)]
L,R,U,D = eval("[[0]*(w+2) for _ in range(h+2)],"*4)
for y in range(h):
	for x in range(w):
		if grid[y][x]:
			L[y+1][x+1] = L[y+1][x]+1
		if grid[y][w-x-1]:
			R[y+1][w-x] = R[y+1][w-x+1]+1
for x in range(w):
	for y in range(h):
		if grid[y][x]:
			U[y+1][x+1] = U[y][x+1]+1
		if grid[h-y-1][x]:
			D[h-y][x+1] = D[h-y+1][x+1]+1
a = 0
for y in range(1,h+1):
	for x in range(1,w+1):
		a = max(a, L[y][x] + R[y][x] + U[y][x] + D[y][x] -3)
print(a)

Solution (Python):
t,*grid = open(0)
h,w = map(int,t.split())
L,R,U,D = eval("[[0]*(w+2) for _ in range(h+2)],"*4)
for y in range(h):
	for x in range(w):
		if grid[y][x]==".":
			L[y+1][x+1] = L[y+1][x]+1
		if grid[y][w-x-1]==".":
			R[y+1][w-x] = R[y+1][w-x+1]+1
for x in range(w):
	for y in range(h):
		if grid[y][x]==".":
			U[y+1][x+1] = U[y][x+1]+1
		if grid[h-y-1][x]==".":
			D[h-y][x+1] = D[h-y+1][x+1]+1
a = 0
for y in range(1,h+1):
	for x in range(1,w+1):
		a = max(a, L[y][x] + R[y][x] + U[y][x] + D[y][x] -3)
print(a)

Solution (Python):
h, w = map(int, input().split())
grid = [None]*h
cnt = [[0 for _ in range(w+1)] for __ in range(h+1)]
for i in range(h):
    grid[i] = list(input())
for i in range(h):
    done = [0]*w
    for j in range(w):
        if grid[i][j] == "
        if done[j] == 1: continue
        l = 0
        while j+l < w:
            if grid[i][j+l] == "
            l += 1
        for k in range(l):
            cnt[i][j+k] += l
            done[j+k] = 1
for j in range(w):
    done = [0]*h
    for i in range(h):
        if grid[i][j] == "
        if done[i] == 1: continue
        l = 0
        while i+l < h:
            if grid[i+l][j] == "
            l += 1
        for k in range(l):
            cnt[i+k][j] += l
            done[i+k] = 1
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, cnt[i][j]-1)
print(ans)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    a,b,c = LI()
    ans = 10 ** 5
    ans = min(ans, a + b)
    ans = min(ans, a + c)
    ans = min(ans, c + b)
    print(ans)
    return


def B():
    n = II()
    w = LI()
    ans = inf
    for i in range(n):
        ans = min(ans, abs(sum(w[:i]) - sum(w[i:])))
    print(ans)
    return


def C():
    n, m = LI()
    a = IR(m)+[inf]
    dp = [0] * (n + 3)
    dp[0] = 1
    for i in range(n + 1):
        if a[bisect_left(a, i + 1)] != i + 1:
            dp[i + 1] += dp[i] % mod
        if a[bisect_left(a, i + 2)] != i + 2:
            dp[i + 2] += dp[i] % mod
    print(dp[n] % mod)
    return


def D():
    h, w = LI()
    s = SR(h)
    dp = [[0] * w for _ in range(h)]
    for x in range(w):
        for y in range(h):
            if s[y][x] == ".":
                dp[y][x] += 1
    for y in range(h):
        x = 0
        q = 0
        while 0 <= x < w:
            if s[y][x] == ".":
                dp[y][x] += q
                q += 1
            else:
                q = 0
            x += 1
        x = w - 1
        q = 0
        while 0 <= x < w:
            if s[y][x] == ".":
                dp[y][x] += q
                q += 1
            else:
                q = 0
            x -= 1
    for x in range(w):
        y = 0
        q = 0
        while 0 <= y < h:
            if s[y][x] == ".":
                dp[y][x] += q
                q += 1
            else:
                q = 0
            y += 1
        y = h - 1
        q = 0
        while 0 <= y < h:
            if s[y][x] == ".":
                dp[y][x] += q
                q += 1
            else:
                q = 0
            y -= 1
    print(max(map(lambda x: max(x), dp)))
    return



if __name__ == '__main__':
    D()

Solution (Python):
H,W = map(int,input().split())
S = [input() for _ in range(H)]
L,R,D,U = [[[0]*W for _ in range(H)] for i in range(4)]
 
for h in range(H):
    for w in range(W):
        if S[h][w] == '.':
            L[h][w] = L[h][w-1]+1
            U[h][w] = U[h-1][w]+1
        if S[h][W-1-w] == '.':
            R[h][-w-1] = R[h][-w]+1
        if S[H-1-h][w] == '.':
            D[-h-1][w] = D[-h][w]+1
 
ans = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == '.':
            ans = max(ans,L[h][w]+U[h][w]+R[h][w]+D[h][w]-3)
 
print(ans)

Solution (Python):
H, W = [int(_) for _ in input().split()]

S = [input() for _ in range(H)]
memo = [[0] * W for _ in range(H)]

for h in range(H):
    done = [False] * W
    for w in range(W):
        if S[h][w] == '
        if done[w]: continue

        tmp = w
        cnt = 0
        while tmp < W:
            if S[h][tmp] == '
            cnt += 1
            tmp += 1

        for i in range(w, tmp):
            memo[h][i] += cnt
            done[i] = True

for w in range(W):
    done = [False] * H
    for h in range(H):
        if S[h][w] == '
        if done[h]: continue

        tmp = h
        cnt = 0
        while tmp < H:
            if S[tmp][w] == '
            cnt += 1
            tmp += 1

        for i in range(h, tmp):
            memo[i][w] += cnt
            done[i] = True

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

Solution (Python):
import numpy as np

H, W = map(int, input().split())
S = np.array([list(input()) 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 h in range(H):
    U[h] = (U[h - 1] + 1) * S[h]
    D[-h - 1] = (D[-h] + 1) * S[-h - 1]
for w in range(W):
    L[:, w] = (L[:, w - 1] + 1) * S[:, w]
    R[:, -w - 1] = (R[:, -w] + 1) * S[:, -w - 1]
print(np.max(U + D + L + R) - 3)

Solution (Python):
h, w = map(int, input().split())
sL = [input() for _ in range(h)]
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)]
for i in range(h):  
    for j in range(w):  
        if sL[i][j] != "
            if j == 0:
                L[i][j] = 1
            else:
                L[i][j] = L[i][j-1] + 1
        else:
            L[i][j] = 0
for i in range(h):  
    for j in range(w-1, -1, -1):  
        if sL[i][j] != "
            if j == w-1:
                R[i][j] = 1
            else:
                R[i][j] = R[i][j+1] + 1
        else:
            R[i][j] = 0
for j in range(w):  
    for i in range(h):  
        if sL[i][j] != "
            if i == 0:
                U[i][j] = 1
            else:
                U[i][j] = U[i-1][j] + 1
        else:
            U[i][j] = 0
for j in range(w):  
    for i in range(h-1, -1, -1):  
        if sL[i][j] != "
            if i == h-1:
                D[i][j] = 1
            else:
                D[i][j] = D[i+1][j] + 1
        else:
            D[i][j] = 0
max_ = 0
sum_ = 0
for i in range(h):
    for j in range(w):
        sum_ = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
        if sum_ > max_:
            max_ = sum_
print(max_)

Solution (Python):
h,w = map(int,input().split())
S = [(input()+'
Rows = []
Columns = []
for i in range(h):
    Row = []
    row = 0
    for j in range(w+1):
        if S[i][j] == '.':
            row += 1
        else:
            if row > 0:
                Row += [row]
            row = 0
            Row += [row]
    Rows += [Row]
for j in range(w):
    Column = []
    column = 0
    for i in range(h+1):
        if S[i][j] == '.':
            column += 1
        else:
            if column > 0:
                Column += [column]
            column = 0
            Column += [column]
    Columns += [Column]
mRows = []
mColumns = []
for i in range(h):
  mRow= []
  for j in range(len(Rows[i])):
    mRow += [Rows[i][j]]*max(1,Rows[i][j])
  mRows += [mRow]
for i in range(w):
  mColumn= []
  for j in range(len(Columns[i])):
    mColumn += [Columns[i][j]]*max(1,Columns[i][j])
  mColumns += [mColumn]
ans = 0
for i in range(h):
  for j in range(w):
    ans = max(ans,mRows[i][j]+mColumns[j][i]-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
    for j in reversed(range(w)):
        if S[i][j] == '.':
            if j == w-1:
                R[i][j] = 1
            else:
                R[i][j] = R[i][j+1] + 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
    for i in reversed(range(h)):
        if S[i][j] == '.':
            if 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)

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)]
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
    for j in reversed(range(w)):
        if S[i][j] == '.':
            if j == w-1:
                R[i][j] = 1
            else:
                R[i][j] = R[i][j+1] + 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
    for i in reversed(range(h)):
        if S[i][j] == '.':
            if 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)

Solution (Python):
h, w = map(int, input().split())
S = [list(input()) for _ in range(h)]
L = [[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
R = [[0] * w for _ in range(h)]
for i in range(h):
    for j in reversed(range(w)):
        
        
        if S[i][j] == '.':
            if j == w-1:
                R[i][j] = 1
            else:
                R[i][j] = R[i][j+1] + 1
U = [[0] * w for _ in range(h)]
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
D = [[0] * w for _ in range(h)]
for j in range(w):
    for i in reversed(range(h)):
        
        
        if S[i][j] == '.':
            if 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)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


h, w = LI()
L = SR(h)
u = [[0]*w for _ in range(h)]
d = [[0]*w for _ in range(h)]
l = [[0]*w for _ in range(h)]
r = [[0]*w for _ in range(h)]
for y in range(h):
    l[y][0] = 1 if L[y][0] == '.' else 0
    for x in range(1, w):
        if L[y][x] == '.':
            l[y][x] = l[y][x-1] + 1



for y in range(h):
    r[y][w-1] = 1 if L[y][w-1] == '.' else 0
    for x in range(w-2, -1, -1):
        if L[y][x] == '.':
            r[y][x] = r[y][x+1] + 1



for x in range(w):
    u[0][x] = 1 if L[0][x] == '.' else 0
    for y in range(1, h):
        if L[y][x] == '.':
            u[y][x] = u[y-1][x] + 1


for x in range(w):
    d[h-1][x] = 1 if L[h-1][x] == '.' else 0
    for y in range(h-2, -1, -1):
        if L[y][x] == '.':
            d[y][x] = d[y+1][x] + 1



print(max([u[y][x] + d[y][x] + l[y][x] + r[y][x] for y in range(h) for x in range(w)]) - 3)

Solution (Python):

def main():
    H, W, *S = open(0).read().split()
    H, W = int(H), int(W)
    L, R = [[0] * W for _ in range(H)], [[0] * W for _ in range(H)]
    U, D = [[0] * W for _ in range(H)], [[0] * W for _ in range(H)]
    for x1 in range(H):
        for y1 in range(W):
            if S[x1][y1] == ".":  
                U[x1][y1] = U[x1 - 1][y1] + 1
                L[x1][y1] = L[x1][y1 - 1] + 1
            x2, y2 = -x1 - 1, -y1 - 1
            if S[x2][y2] == ".":  
                D[x2][y2] = D[x2 + 1][y2] + 1
                R[x2][y2] = R[x2][y2 + 1] + 1
    ans = -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)


if __name__ == "__main__":
    main()

Solution (Python):

def main():
    H, W, *S = open(0).read().split()
    H, W = int(H), int(W)
    L, R = [[0] * W for _ in range(H)], [[0] * W for _ in range(H)]
    U, D = [[0] * W for _ in range(H)], [[0] * W for _ in range(H)]
    for x1 in range(H):
        for y1 in range(W):
            if S[x1][y1] == ".":  
                U[x1][y1] = U[x1 - 1][y1] + 1
                L[x1][y1] = L[x1][y1 - 1] + 1
            x2, y2 = -x1 - 1, -y1 - 1
            if S[x2][y2] == ".":  
                D[x2][y2] = D[x2 + 1][y2] + 1
                R[x2][y2] = R[x2][y2 + 1] + 1
    ans = max(L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3 for i in range(H) for j in range(W))
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

def main():
    H, W, *S = open(0).read().split()
    H, W = int(H), int(W)
    L, R = [[0] * W for _ in range(H)], [[0] * W for _ in range(H)]
    U, D = [[0] * W for _ in range(H)], [[0] * W for _ in range(H)]
    for x1 in range(H):
        for y1 in range(W):
            if S[x1][y1] == ".":  
                U[x1][y1] = U[x1 - 1][y1] + 1
                L[x1][y1] = L[x1][y1 - 1] + 1
            x2, y2 = -x1 - 1, -y1 - 1
            if S[x2][y2] == ".":  
                D[x2][y2] = D[x2 + 1][y2] + 1
                R[x2][y2] = R[x2][y2 + 1] + 1
    ans = -float("inf")
    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):

def main():
    H, W, *S = open(0).read().split()
    H, W = int(H), int(W)
    L, R = [[0] * W for _ in range(H)], [[0] * W for _ in range(H)]
    U, D = [[0] * W for _ in range(H)], [[0] * W for _ in range(H)]
    for x1 in range(H):
        for y1 in range(W):
            if S[x1][y1] == ".":  
                U[x1][y1] = U[x1 - 1][y1] + 1
                L[x1][y1] = L[x1][y1 - 1] + 1
            x2, y2 = -x1 - 1, -y1 - 1
            if S[x2][y2] == ".":  
                D[x2][y2] = D[x2 + 1][y2] + 1
                R[x2][y2] = R[x2][y2 + 1] + 1
    ans = -float("inf")
    for i in range(H):
        for j in range(W):
            x = L[i][j] + R[i][j] + U[i][j] + D[i][j] - 3
            if x > ans:
                ans = x
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
h, w = map(int, input().split())
ls = [input().strip() for _ in range(h)]
counts = [[[-1] * w for _ in range(h)] for _ in range(4)]

for y in range(h):
    for x in range(w):
        if ls[y][x] == '
            counts[0][y][x] = 0
            counts[2][y][x] = 0
        else:
            if x == 0:
                counts[0][y][x] = 1
            else:
                counts[0][y][x] = counts[0][y][x - 1] + 1
            if y == 0:
                counts[2][y][x] = 1
            else:
                counts[2][y][x] = counts[2][y - 1][x] + 1

        yy = h - 1 - y
        xx = w - 1 - x
        if ls[yy][xx] == '
            counts[1][yy][xx] = 0
            counts[3][yy][xx] = 0
        else:
            if xx == w - 1:
                counts[1][yy][xx] = 1
            else:
                counts[1][yy][xx] = counts[1][yy][xx + 1] + 1
            if yy == h - 1:
                counts[3][yy][xx] = 1
            else:
                counts[3][yy][xx] = counts[3][yy + 1][xx] + 1

res = 0
for y in range(h):
    for x in range(w):
        val = -3
        for i in range(4):
            val += counts[i][y][x]
        res = max(res, val)
print(res)

Solution (Python):
h, w = map(int, input().split())
ls = [input().strip() for _ in range(h)]
counts = [[[-1] * w for _ in range(h)] for _ in range(4)]

for y in range(h):
    for x in range(w):
        if ls[y][x] == '
            counts[0][y][x] = 0
        else:
            if x == 0:
                counts[0][y][x] = 1
            else:
                counts[0][y][x] = counts[0][y][x - 1] + 1
        yy = h - 1 - y
        xx = w - 1 - x
        if ls[yy][xx] == '
            counts[1][yy][xx] = 0
        else:
            if x == 0:
                counts[1][yy][xx] = 1
            else:
                counts[1][yy][xx] = counts[1][yy][xx + 1] + 1

        if ls[y][x] == '
            counts[2][y][x] = 0
        else:
            if y == 0:
                counts[2][y][x] = 1
            else:
                counts[2][y][x] = counts[2][y - 1][x] + 1
        yy = h - 1 - y
        xx = w - 1 - x
        if ls[yy][xx] == '
            counts[3][yy][xx] = 0
        else:
            if y == 0:
                counts[3][yy][xx] = 1
            else:
                counts[3][yy][xx] = counts[3][yy + 1][xx] + 1

res = 0
for y in range(h):
    for x in range(w):
        val = -3
        for i in range(4):
            val += counts[i][y][x]
        res = max(res, val)

print(res)

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

L = [[0 for _ in range(w)] for _ in range(h)]
R = [[0 for _ in range(w)] for _ in range(h)]
D = [[0 for _ in range(w)] for _ in range(h)]
U = [[0 for _ in range(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 i == 0:
        D[i][j] = 1
      else:
        D[i][j] = D[i-1][j]+1
      if i == h-1:
        U[i][j] = 1
      else:
        U[i][j] = U[i+1][j]+1
  for j in range(w-1, -1, -1):
    if s[i][j] == '.':
      if j == w-1:
        R[i][j] = 1
      else:
        R[i][j] = R[i][j+1]+1

for i in range(h-1, -1, -1):
  for j in range(w):
    if s[i][j] == '.':
      if i == h-1:
        U[i][j] = 1
      else:
        U[i][j] = U[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 = []
for i in range(H):
  ss = input()
  S.append(ss)
L = [[-1]*W for i in range(H)]
R = [[-1]*W for i in range(H)]
U = [[-1]*W for i in range(H)]
D = [[-1]*W for i in range(H)]
for i in range(H):
  n = -1
  for j in range(W):
    if S[i][j] == "
      n = j
    L[i][j] = j-n
  n = W
  for j in reversed(range(W)):
    if S[i][j] == "
      n = j
    R[i][j] = n-j
for j in range(W):
  n = -1
  for i in range(H):
    if S[i][j] == "
      n = i
    U[i][j] = i-n
  n = H
  for i in reversed(range(H)):
    if S[i][j] == "
      n = i
    D[i][j] = n-i


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

Solution (Python):

import sys
import numpy as np

def solve():
    H, W = list(map(int, sys.stdin.readline().split()))
    grid = []
    for _ in range(H):
        grid.append(list(input()))
    grid = (np.array(grid) == ".")*1  

    

    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 i in range(W):
        if i == 0:
            L[:, i] = grid[:, i]
        else:
            L[:, i] = (L[:, i-1] + 1) * grid[:, i]

    
    for i in range(W-1, -1, -1):
        if i == W-1:
            R[:, i] = grid[:, i]
        else:
            R[:, i] = (R[:, i+1] + 1) * grid[:, i]

    
    for i in range(H):
        if i == 0:
            U[i] = grid[i]
        else:
            U[i] = (U[i-1] + 1) * grid[i]

    
    for i in range(H-1, -1, -1):
        if i == H-1:
            D[i] = grid[i]
        else:
            D[i] = (D[i+1] + 1) * grid[i]

    
    
    ans_grid = L + R + U + D - 3
    ans = np.max(ans_grid)
    print(ans)


if __name__ == "__main__":
    solve()

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

L = [[1]*W for i in range(H)]
R = [[1]*W for i in range(H)]
U = [[1]*W for i in range(H)]
D = [[1]*W for i in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == "
            L[i][j] = 0
            U[i][j] = 0
        elif i == 0 and j == 0:
            continue
        elif i == 0:
            L[i][j] = L[i][j-1] + 1
        elif j == 0:
            U[i][j] = U[i-1][j] + 1
        else:
            L[i][j] = L[i][j-1] + 1
            U[i][j] = U[i-1][j] + 1


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

print(ans)

Solution (Python):
h, w = map(int, input().split())

s = [input() for i in range(h)]

init = lambda :[[0] * (w+2) for i in range(h+2)]
r, l, u, d = init(), init(), init(), init()

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

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

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

print(ans-3)

Solution (Python):
import numpy as np

H,W=map(int,input().split())
S=np.array([list(input()) 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):
H,W=map(int,input().split())
A=[list(map(lambda x:False if x=='

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(1,W):
		if A[i][j]:
			L[i][j]=int(A[i][j-1])+L[i][j-1]

for i in range(H):
	for j in range(W-1)[::-1]:
		if A[i][j]:
			R[i][j]=int(A[i][j+1])+R[i][j+1]

for i in range(1,H):
	for j in range(W):
		if A[i][j]:
			U[i][j]=int(A[i-1][j])+U[i-1][j]


for i in range(H-1)[::-1]:
	for j in range(W):
		if A[i][j]:
			D[i][j]=int(A[i+1][j])+D[i+1][j]

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]+1)

print(ans)