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

import numpy as np
H,W = map(int,input().split())
L = np.zeros((H,W),int)
R = np.zeros((H,W),int)
D = np.zeros((H,W),int)
U = np.zeros((H,W),int)
S = np.array([list(input()) for h in range(H)])=="."

for h in range(H):
  U[h] = S[h]*(U[h-1]+1)
  D[-h-1] = S[-h-1]*(D[-h]+1)

for w in range(W):
  L[:,w] = S[:,w]*(L[:,w-1]+1)
  R[:,-w-1] = S[:,-w-1]*(R[:,-w]+1)

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

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

for i in range(h):
    count = 0
    start = 0
    end = 0
    for j in range(w):
        if s[i][j] != "
            count += 1
        else:
            for z in range(start, end):
                s[i][z] = count
            start = end+1
            count = 0
        end += 1
    for z in range(start, end):
        s[i][z] = count
    
ans = 0

for i in range(w):
    count = 0
    start = 0
    end = 0
    for j in range(h):
        if s[j][i] != "
            count += 1
        else:
            for z in range(start, end):
                s[z][i] += count
            start = end+1
            count = 0
        end += 1
    for z in range(start, end):
        s[z][i] += count

for i in range(h):
    
    for j in range(w):

        if s[i][j] != "
            ans = max(ans, s[i][j])
print(ans-1)

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

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

yStarts = [-1] * w
yStrks = [0] * w

for y in range(h):
    xStart = -1
    xStrk = 0

    for x in range(w):
        if grid[y][x] == ".":
            if xStart == -1:
                xStart = x
            xStrk += 1

            if yStarts[x] == -1:
                yStarts[x] = y
            yStrks[x] += 1

        if grid[y][x] == "
            if xStart != -1:
                xEnd = x if grid[y][x] == "." else x-1

                for x2 in range(xStart, xEnd+1):
                    cnt[y][x2] += (xEnd-xStart)+1

            xStart = -1
            xStrk = 0

        if grid[y][x] == "
            if yStarts[x] != -1:
                yEnd = y if grid[y][x] == "." else y-1

                for y2 in range(yStarts[x], yEnd+1):
                    cnt[y2][x] += (yEnd-yStarts[x])+1

            yStarts[x] = -1
            yStrks[x] = 0

ans = 0
for y in range(h):
    for x in range(w):
        ans = max(ans, cnt[y][x]-1)

print(ans)

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

w1=[[]for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j]=='
            w1[i].append(j)
    w1[i].append(W)

w2=[[0]*W for _ in range(H)]
for i in range(H):
    k=0
    L=-1
    R=w1[i][k]
    for j in range(W):
        if S[i][j]=='
            L=w1[i][k]
            k+=1
            R=w1[i][k]
            continue
        w2[i][j]=R-L-1

h1=[[]for _ in range(W)]
for j in range(W):
    for i in range(H):
        if S[i][j]=='
            h1[j].append(i)
    h1[j].append(H)

h2=[[0]*W for _ in range(H)]
for j in range(W):
    k=0
    L=-1
    R=h1[j][k]
    for i in range(H):
        if S[i][j]=='
            L=h1[j][k]
            k+=1
            R=h1[j][k]
            continue
        h2[i][j]=R-L-1

print(max(w2[i][j]+h2[i][j]-1 for i in range(H)for j in range(W)))

Solution (Python):

import sys
input = lambda: sys.stdin.readline().strip()
h, w = [int(x) for x in input().split()]
g = [input() for i in range(h)]
dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
hit = [[[0 for j in range(w)] for i in range(h)] for dire in dirs]
for d, dire in enumerate(dirs):
    di, dj = dire
    for i in range(h) if di < 0 else reversed(range(h)):
        for j in range(w) if dj < 0 else reversed(range(w)):
            if g[i][j] != '
                hit[d][i][j] = (hit[d][i + di][j + dj] if 0 <= i + di < h and 0 <= j + dj < w else 0) + 1
print(max(sum(hit[d][i][j] for d in range(len(dirs))) - 3 for i in range(h) for j in range(w) if g[i][j] != '

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

r = [[0] * w for _ in range(h)]
for i in range(h):
  for j in range(w):
    if map[i][j] == ".":
      if j == 0:
        r[i][j] = 1
      else:
        r[i][j] = r[i][j-1] + 1

l = [[0] * w for _ in range(h)]
for i in range(h):
  for j in range(w-1, -1, -1):
    if map[i][j] == ".":
      if j == w - 1:
        l[i][j] = 1
      else:
        l[i][j] = l[i][j+1] + 1
        
d = [[0] * w for _ in range(h)]
for i in range(w):
  for j in range(h):
    if map[j][i] == ".":
      if j == 0:
        d[j][i] = 1
      else:
        d[j][i] = d[j-1][i] + 1

u = [[0] * w for _ in range(h)]
for i in range(w):
  for j in range(h-1, -1, -1):
    if map[j][i] == ".":
      if j == h-1:
        u[j][i] = 1
      else:
        u[j][i] = u[j+1][i] + 1
ans = 0
for i in range(h):
  for j in range(w):
    num = l[i][j] + r[i][j] + d[i][j] + u[i][j] - 3
    if num > ans:
      ans = num
print(ans)

Solution (Python):


import numpy as np






INT = lambda: int(input())
INTM = lambda: map(int,input().split())
STRM = lambda: map(str,input().split())
STR = lambda: str(input())
LIST = lambda: list(map(int,input().split()))
LISTS = lambda: list(map(str,input().split()))

def do():
    h,w=INTM()
    ban=np.zeros((h,w),dtype=np.int16)
    for i in range(h):
        s=STR()
        for i1 in range(len(s)):
            if s[i1]==".":
                ban[i][i1]=1

    left =np.zeros((h,w),dtype=np.int16)
    right=np.zeros((h,w),dtype=np.int16)
    up   =np.zeros((h,w),dtype=np.int16)
    down =np.zeros((h,w),dtype=np.int16)
    
    for i in range(w):
        i2=w-1-i
        if i==0:
            left[:,i]=ban[:,i]
            right[:,i2]=ban[:,i2]
        else:
            left[:,i]=ban[:,i]*(left[:,i-1]+1)
            right[:,i2]=ban[:,i2]*(right[:,i2+1]+1)
    
    for i in range(h):
        i2=h-1-i
        if i==0:
            up[i,:]=ban[i,:]
            down[i2,:]=ban[i2,:]
        else:
            up[i,:]=ban[i,:]*(up[i-1,:]+1)
            down[i2,:]=ban[i2,:]*(down[i2+1,:]+1)
    

    anslist=down+up+right+left
    ans=0
    for i in anslist:
        ans=max(ans,max(i))
    print(ans-3)


if __name__=='__main__':
    do()

Solution (Python):
H, W = list(map(int, input().split()))
maps = [['']*(W+2) for _ in range(H+2)]
maps[0] = ['
for i in range(H):
    maps[i+1] = ['
maps[H+1] = ['

ans = 0
L = [[[0, 0] for _ in range(W)] for _ in range(H)]
for i in range(H):
    for j in range(W):
        if maps[i+1][j+1] == '
            continue
        if j >= 1 and L[i][j-1][1] > 0:
            L[i][j][1] = L[i][j-1][1]
        else:
            u = j+1
            while maps[i+1][u] == '.':
                u += 1
            L[i][j][1] = u-j-1
        if i >= 1 and L[i-1][j][0] > 0:
            L[i][j][0] = L[i-1][j][0]
        else:
            u = i+1
            while maps[u][j+1] == '.':
                u += 1
            L[i][j][0] = u-i-1
        ans = max(ans, L[i][j][0]+L[i][j][1]-1)
print(ans)

Solution (Python):


H,W=map(int,input().split())
S=[input() for _ in [0]*H]
Lx=[[0]*W for _ in [0]*H]
Ly=[[0]*W for _ in [0]*H]

def search_x(x,y):
    i=x
    while 1:
        i+=1
        if i<W:
            if S[y][i]=='
                break
        else:
            break
    return i-x

def search_y(x,y):
    j=y
    while 1:
        j+=1
        if j<H:
            if S[j][x]=='
                break
        else:
            break
    return j-y

def set_x(x,y,p):
    i=x
    Lx[y][i]=p
    while 1:
        i+=1
        if i<W:
            if S[y][i]=='
                break
            else:
                Lx[y][i]=p
        else:
            break

def set_y(x,y,p):
    j=y
    Ly[j][x]=p
    while 1:
        j+=1
        if j<H:
            if S[j][x]=='
                break
            else:
                Ly[j][x]=p
        else:
            break

res=0
for y in range(H):
    for x in range(W):
        if S[y][x]=='.':
            if Lx[y][x]==0:
                w=search_x(x,y)
                set_x(x,y,w)
            if Ly[y][x]==0:
                Ly[y][x]==0
                h=search_y(x,y)
                set_y(x,y,h)
            res=max(Lx[y][x]+Ly[y][x]-1,res)
print(res)

Solution (Python):
H, W = map(int, input().split())
G = [list(input()) for i in range(H)]


up = [[0] * W for i in range(H)]  
right = [[0] * W for i in range(H)]  
down = [[0] * W for i in range(H)]  
left = [[0] * W for i in range(H)]  



for w in range(W):
    for h in range(1, H):
        if G[h - 1][w] == '
            continue
        up[h][w] = up[h - 1][w] + 1


for h in range(H):
    for w in reversed(range(W - 1)):
        if G[h][w + 1] == '
            continue
        right[h][w] = right[h][w + 1] + 1


for w in range(W):
    for h in reversed(range(H - 1)):
        if G[h + 1][w] == '
            continue
        down[h][w] = down[h + 1][w] + 1


for h in range(H):
    for w in range(1, W):
        if G[h][w - 1] == '
            continue
        left[h][w] = left[h][w - 1] + 1


ans = 0
for h in range(H):
    for w in range(W):
        if G[h][w] == '
            continue
        ans = max(ans, up[h][w] + right[h][w] + down[h][w] + left[h][w] + 1)

print(ans)

Solution (Python):
h,w=map(int, input().split())
maps=[[0]*w for i in range(h)]
for i in range(h):
    s=input()
    for j in range(w):
        if s[j]=="
            maps[i][j]=-1
    
maps_l=[[0]*w for i in range(h)]
maps_r=[[0]*w for i in range(h)]
maps_u=[[0]*w for i in range(h)]
maps_d=[[0]*w for i in range(h)]

for i in range(h):
    for j in range(w):
        if maps[i][j]==-1:
            maps_l[i][j]=0
        elif j==0:
            maps_l[i][j]=1
        else:
            maps_l[i][j]=maps_l[i][j-1]+1

for i in range(h):
    for j in range(w-1,-1,-1):
        if maps[i][j]==-1:
            maps_r[i][j]=0
        elif j==w-1:
            maps_r[i][j]=1
        else:
            maps_r[i][j]=maps_r[i][j+1]+1

for j in range(w):
    for i in range(h):
        if maps[i][j]==-1:
            maps_d[i][j]=0
        elif i==0:
            maps_d[i][j]=1
        else:
            maps_d[i][j]=maps_d[i-1][j]+1

for j in range(w):
    for i in range(h-1,-1,-1):
        if maps[i][j]==-1:
            maps_u[i][j]=0
        elif i==h-1:
            maps_u[i][j]=1
        else:
            maps_u[i][j]=maps_u[i+1][j]+1
ans=0
for i in range(h):
    for j in range(w):
        if maps[i][j]!=-1:
            ans=max(ans,maps_u[i][j]+maps_d[i][j]+maps_r[i][j]+maps_l[i][j]-3)

print(ans)

Solution (Python):
h,w=map(int,input().split())
S=[]
for i in range(h):
    S.append(input())

tab=[[0 for i in range(w)] for q in range(h)]

cnt=0
for i in range(h):
    cnt=0
    for q in range(w):
        if S[i][q]==".":
            cnt+=1
        else:
            cnt=0
        tab[i][q]+=cnt



cnt=0
for i in range(h):
    cnt=0
    for q in range(w-1,-1,-1):
        if S[i][q]==".":
            cnt+=1
        else:
            cnt=0
        tab[i][q]+=cnt



cnt=0
for q in range(w):
    cnt=0
    for i in range(h):
        if S[i][q]==".":
            cnt+=1
        else:
            cnt=0
        tab[i][q]+=cnt



cnt=0
for q in range(w):
    cnt=0
    for i in range(h-1,-1,-1):
        if S[i][q]==".":
            cnt+=1
        else:
            cnt=0
        tab[i][q]+=cnt

print(max([max(col) for col in tab])-3)

Solution (Python):






import numpy as np





H, W = map(int, input().split())
S = np.ones((H, W), dtype=np.bool)
for i in range(H):
    S[i] = [s == "." for s in input()]





up = np.zeros((H, W), dtype=np.int16)
down = np.zeros((H, W), dtype=np.int16)
left = np.zeros((H, W), dtype=np.int16)
right = np.zeros((H, W), dtype=np.int16)


up[0, :] = S[0, :]
for h in range(1, H):
    up[h, :] = up[h - 1, :] + 1
    up[h, :] *= S[h, :]


down[H - 1, :] = S[H - 1, :]
for h in reversed(range(0, H - 1)):
    down[h, :] = down[h + 1, :] + 1
    down[h, :] *= S[h, :]


left[:, 0] = S[:, 0]
for w in range(1, W):
    left[:, w] = left[:, w - 1] + 1
    left[:, w] *= S[:, w]


right[:, W - 1] = S[:, W - 1]
for w in reversed(range(0, W - 1)):
    right[:, w] = right[:, w + 1] + 1
    right[:, w] *= S[:, w]

ans = np.max(up + down + left + right - 3)
print(ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy
from operator import itemgetter

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  



H, W = na()
S = [ns() for _ in range(H)]
tmp = [[0] * W for _ in range(H)]

tmp2 = [[0] * W for _ in range(H)]
for i in range(H):
    ct = 0
    for j in range(W):
        if S[i][j] == '
            if ct != 0:
                for k in range(ct):
                   tmp[i][j-(k+1)] += ct 
            ct = 0
        else:
            ct += 1
    if ct != 0:
        for k in range(ct):
            tmp[i][j-k] += ct 
    

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

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

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

yoko = [[0]*W for _ in range(H)]
tate = [[0]*W for _ in range(H)]

def f(l):
    print("\n".join("".join(map(str, row)) for row in l))

for h in range(H):
    if S[h][0] == ".":
        yoko[h][0] = 1
    else:
        yoko[h][0] = 0

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

for h in range(H):
    for w in range(W-2, -1, -1):
        if S[h][w]=="." and S[h][w+1]==".":
            yoko[h][w] = yoko[h][w+1]

for w in range(W):
    if S[0][w] == ".":
        tate[0][w] = 1
    else:
        tate[0][w] = 0

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

for w in range(W):
    for h in range(H-2, -1, -1):
        if S[h][w]=="." and S[h+1][w]==".":
            tate[h][w] = tate[h+1][w]

ans = 0

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

print(ans)

Solution (Python):
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))

H,W=mint()
S=[input() for _ in range(H)]
C=[[0]*W for _ in range(H)]
for i in range(H):
    l=0
    for r in range(W):
        if S[i][r]=='.':
            continue
        tmp=r-l
        while l<r:
            C[i][l]+=tmp
            l+=1
        l=r+1
    tmp=W-l
    while l<W:
        C[i][l]+=tmp
        l+=1
for j in range(W):
    l=0
    for r in range(H):
        if S[r][j]=='.':
            continue
        tmp=r-l
        while l<r:
            C[l][j]+=tmp
            l+=1
        l=r+1
    tmp=H-l
    while l<H:
        C[l][j]+=tmp
        l+=1
print(max([max(c) for c in C])-1)

Solution (Python):
H, W = map(int, input().split())
S = []
l1 = []
for i in range(H):
  s = str(input())
  S.append(s)
  tmp = []
  cnt = 0
  flag = False
  for j in s:
    if flag:
      if j == '.':
        cnt += 1
      else:
        for k in range(cnt):
          tmp.append(cnt)
        cnt = 0
        tmp.append(0)
        flag = False
    else:
      if j == '.':
        flag = True
        cnt += 1
      else:
        tmp.append(0)
  if cnt > 0:
    for k in range(cnt):
      tmp.append(cnt)
  l1.append(tmp)

l2 = []
for i in range(W):
  tmp = []
  cnt = 0
  flag = False
  for j in range(H):
    x = S[j][i]
    if flag:
      if x == '.':
        cnt += 1
      else:
        for k in range(cnt):
          tmp.append(cnt)
        cnt = 0
        tmp.append(0)
        flag = False
    else:
      if x == '.':
        flag = True
        cnt += 1
      else:
        tmp.append(0)
  if cnt > 0:
    for k in range(cnt):
      tmp.append(cnt)
  l2.append(tmp)

ans = [[0]*W for i in range(H)]
m = 0
for i in range(H):
  for j in range(W):
    if (l1[i][j]>0) and (l2[j][i]>0):
      ans[i][j] = l1[i][j] + l2[j][i] - 1
    else:
      ans[i][j] = l1[i][j] + l2[j][i]
    m = max(m, ans[i][j])
print(m)

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


H,W=map(int,input().split())
S=[]
for i in range(H):
  S.append(list(input()))

rowGroups=UnionFind(H*W)
colGroups=UnionFind(H*W)

for i in range(H):
  for j in range(W):
    if j-1>=0 and S[i][j-1]=='.' and S[i][j]=='.':
      rowGroups.union(i*W+j,i*W+j-1)
    if i-1>=0 and S[i-1][j]=='.' and S[i][j]=='.':
      colGroups.union(i*W+j,(i-1)*W+j)
ans=0
for i in range(H):
  for j in range(W):
    ans=max(rowGroups.size(W*i+j)+colGroups.size(W*i+j)-1,ans)
print(ans)

Solution (Python):
import numpy as np

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

t = np.zeros((h, w), dtype=np.int32)
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            t[i][j] = 1

l = np.zeros((h, w), dtype=np.int32)
r = np.zeros((h, w), dtype=np.int32)
u = np.zeros((h, w), dtype=np.int32)
d = np.zeros((h, w), dtype=np.int32)

for i in range(w):
    if i == 0:
        l[:, i] = t[:, i]
    else:
        l[:, i] = (l[:, i-1] + 1) * t[:, i]

for i in range(w-1, -1, -1):
    if i == w-1:
        r[:, i] = t[:, i]
    else:
        r[:, i] = (r[:, i+1] + 1) * t[:, i]

for i in range(h):
    if i == 0:
        u[i] = t[i]
    else:
        u[i] = (u[i-1] + 1) * t[i]

for i in range(h-1, -1, -1):
    if i == h-1:
        d[i] = t[i]
    else:
        d[i] = (d[i+1] + 1) * t[i]

lrud = l+r+u+d-3
print(np.max(lrud))

Solution (Python):
import numpy as np
H,W = map(int,input().split())
L = np.zeros((H,W),int)
R = np.zeros((H,W),int)
D = np.zeros((H,W),int)
U = np.zeros((H,W),int)
S = np.array([list(input()) for h in range(H)])=="."

for h in range(H):
  U[h] = S[h]*(U[h-1]+1)
  D[-h-1] = S[-h-1]*(D[-h]+1)

for w in range(W):
  L[:,w] = S[:,w]*(L[:,w-1]+1)
  R[:,-w-1] = S[:,-w-1]*(R[:,-w]+1)

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

Solution (Python):
import sys



def input():
    return sys.stdin.readline().strip()


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    h, w = input_int_list()
    grid = []
    for i in range(h):
        grid.append(list(input()))

    ver_cnt = [[None for _ in range(w)] for _ in range(h)]
    hor_cnt = [[None for _ in range(w)] for _ in range(h)]

    for i in range(h):
        for j in range(w):
            if grid[i][j] == ".":
                
                if not hor_cnt[i][j]:
                    j_end = j
                    cnt = 0
                    while j_end < w:
                        if grid[i][j_end] == "
                            break
                        else:
                            j_end += 1
                            cnt += 1
                    for _j in range(j, j_end):
                        hor_cnt[i][_j] = cnt
                
                if not ver_cnt[i][j]:
                    i_end = i
                    cnt = 0
                    while i_end < h:
                        if grid[i_end][j] == "
                            break
                        else:
                            i_end += 1
                            cnt += 1
                    for _i in range(i, i_end):
                        ver_cnt[_i][j] = cnt
    ans = 0

    for i in range(h):
        for j in range(w):
            if grid[i][j] != "
                ans = max(ans, ver_cnt[i][j] + hor_cnt[i][j] - 1)
    print(ans)


if __name__ == "__main__":
    main()

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

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

a = [[0] * W for _ in range(H)] 
b = [[0] * W for _ in range(H)] 
c = [[0] * H for _ in range(W)] 
d = [[0] * H for _ in range(W)] 

for x in range(H):
    for y in range(W):
        if S[x][y] == '
            a[x][y] = -1
        elif y > 0:
            a[x][y] = a[x][y-1] + 1
            
for x in range(H):
    for y in range(W-1,-1,-1):
        if S[x][y] == '
            b[x][y] = -1
        elif y < W-1:
            b[x][y] = b[x][y+1] + 1

for y in range(W):
    for x in range(H):
        if S[x][y] == '
            c[y][x] = -1
        elif x > 0:
            c[y][x] = c[y][x-1] + 1

for y in range(W):
    for x in range(H-1,-1,-1):
        if S[x][y] == '
            d[y][x] = -1
        elif x < H-1:
            d[y][x] = d[y][x+1] + 1

ans = 0

for x in range(H):
    for y in range(W):
        if S[x][y] != '
            ans = max(ans,a[x][y]+b[x][y]+c[y][x]+d[y][x]+1)

print(ans)

Solution (Python):
H,W = map(int, input().split())
fs = []
for i in range(H):
    fs.append(input())

lefts = [[0]*W for i in range(H)]
rights = [[0]*W for i in range(H)]
for i in range(H):
    for j in range(W):
        if fs[i][j] == "
            lefts[i][j] = 0
        if fs[i][j] == ".":
            if j == 0:
                lefts[i][j] = 1
            else:
                lefts[i][j] = lefts[i][j-1] + 1
        jr = W - j - 1
        if fs[i][jr] == "
            rights[i][jr] = 0
        else:
            if jr == W-1:
                rights[i][jr] = 1
            else:
                rights[i][jr] = rights[i][jr+1] + 1
ups = [[0]*W for i in range(H)]
downs = [[0]*W for i in range(H)]
for j in range(W):
    for i in range(H):
        if fs[i][j] == "
            ups[i][j] = 0
        else:
            if i == 0:
                ups[i][j] = 1
            else:
                ups[i][j] = ups[i-1][j] + 1
        ir = H - i - 1
        if fs[ir][j] == "
            downs[ir][j] = 0
        else:
            if ir == H-1:
                downs[ir][j] = 1
            else:
                downs[ir][j] = downs[ir+1][j] + 1














ans = 0
for i in range(H):
    for j in range(W):
        x = lefts[i][j] + rights[i][j] + ups[i][j] + downs[i][j]
        
        ans = max(x,ans)
print(ans-3)

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

T = [[0] * W for i in range(H)]  
for i in range(H):
  now = 0
  for j in range(W):
    if HW[i][j] == "
      T[i][j] = 0
      now = 0
    else:
      now += 1
      T[i][j] = now
      
  now = 0    
  for j in range(1, W + 1):
    if T[i][-j] == 0:
      now = 0
    elif now == 0:
      now = T[i][-j]
    else:
      T[i][-j] = now
    
  



Y = [[0] * W for i in range(H)]  
for j in range(W):
  now = 0
  for i in range(H):
    if HW[i][j] == "
      Y[i][j] = 0
      now = 0
    else:
      now += 1
      Y[i][j] = now
      
  now = 0    
  for i in range(1, H + 1):
    if Y[-i][j] == 0:
      now = 0
    elif now == 0:
      now = Y[-i][j]
    else:
      Y[-i][j] = now
    


ans = 0
for i in range(H):
  for j in range(W):
    if T[i][j] != 0 and Y[i][j] != 0:
      ans = max(ans, T[i][j] + Y[i][j] - 1)
      
print(ans)

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

yoko = [[0] * W for i in range(H)]

for i in range(H):
    for j in range(W):
        if yoko[i][j] != 0:
            continue
        elif S[i][j] == "
            yoko[i][j] = 0
        else:
            k = 0
            while S[i][j+k] == ".":
                k += 1
                if j+k == W:
                    break
            yoko[i][j:j+k] = [k] * k

tate = [[0] * W for i in range(H)]

for j in range(W):
    for i in range(H):
        if tate[i][j] != 0:
            continue
        elif S[i][j] == "
            tate[i][j] = 0
        else:
            k = 0
            while S[i+k][j] == ".":
                k += 1
                if i+k == H:
                    break
            for l in range(k):
                tate[i+l][j] = k




ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, yoko[i][j] + tate[i][j] - 1)

print(ans)

Solution (Python):
H,W = map(int,input().split())
Gd = [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 h in range(H):
  for w in range(W):
    if Gd[h][w]=='
      R[h][w]=0
    else:
      if w==0:
        R[h][w]=1
      else:
        R[h][w]=R[h][w-1]+1
    wr=W-w-1
    if Gd[h][wr]=='
      L[h][wr]=0
    else:
      if w==0:
        L[h][wr]=1
      else:
        L[h][wr]=L[h][wr+1]+1

for w in range(W):
  for h in range(H):
    if Gd[h][w]=='
      D[h][w]=0
    else:
      if h==0:
        D[h][w]=1
      else:
        D[h][w]=D[h-1][w]+1
    hr=H-h-1
    if Gd[hr][w]=='
      U[hr][w]=0
    else:
      if h==0:
        U[hr][w]=1
      else:
        U[hr][w]=U[hr+1][w]+1
ret = 0
for w in range(W):
  for h in range(H):
    ret = max(ret, D[h][w]+U[h][w]+R[h][w]+L[h][w]-3)
print(ret)

Solution (Python):
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
t = [[-1] * w for _ in range(h)]
cnt = [0] * 2005
ans = 0
for i in range(h):
    x = 1
    cnt[1] = 0
    for j in range(w):
        if s[i][j] == ".":
            t[i][j] = x
            cnt[x] += 1
        else:
            x += 1
            cnt[x] = 0
    for j in range(w):
        if not t[i][j] == -1:
            t[i][j] = cnt[t[i][j]]
for j in range(w):
    x = 1
    cnt[1] = 0
    for i in range(h):
        if s[i][j] == ".":
            s[i][j] = x
            cnt[x] += 1
        else:
            x += 1
            cnt[x] = 0
    for i in range(h):
        if not s[i][j] == "
            ans = max(ans, t[i][j] + cnt[s[i][j]] - 1)
print(ans)