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 sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

H, W = rl()
S = []
for i in range(H):
  s = rs()
  S.append(s + '
S.append('

tab = [[0 for _ in range(W+1)] for _ in range(H+1)]

for i in range(H):
  k = 0
  prev = -1
  for j in range(W+1):
    if S[i][j] == '
      n = j-prev-1
      while k < j:
        tab[i][k] += n
        k += 1
      tab[i][k] = 0
      k += 1
      prev = j

for j in range(W):
  k = 0
  prev = -1
  for i in range(H+1):
    if S[i][j] == '
      n = i-prev-1
      while k < i:
        tab[k][j] += n - 1
        k += 1
      tab[k][j] = 0
      k += 1
      prev = i

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

Solution (Python):
import sys, math
from collections import defaultdict, deque, Counter
from bisect import bisect_left, bisect_right
from itertools import combinations, permutations, product
from heapq import heappush, heappop
from functools import lru_cache
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 1000000007
sys.setrecursionlimit(1000000)

H, W = rl()
S = []
for i in range(H):
  s = rs()
  S.append(s + '
S.append('

tab = [[0 for _ in range(W+1)] for _ in range(H+1)]

for i in range(H):
  k = 0
  prev = -1
  for j in range(W+1):
    if S[i][j] == '
      n = j-prev-1
      while k < j:
        tab[i][k] += n
        k += 1
      tab[i][k] = 0
      k += 1
      prev = j

for j in range(W):
  k = 0
  prev = -1
  for i in range(H+1):
    if S[i][j] == '
      n = i-prev-1
      while k < i:
        tab[k][j] += n - int(tab[k][j]>0)
        k += 1
      tab[k][j] = 0
      k += 1
      prev = i

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

Solution (Python):
from collections import deque

H,W = map(int, input().split())
Ss = [str(input()) for _ in range(H)]

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

for i in range(H):
    for j in range(W):
        if Ss[i][j] == "
            continue
        else:
            paths = [[i,j]]
            temp = 1
            for k in range(j+1, W):
                if Ss[i][k] == ".":
                    temp+=1
                    paths.append([i,k])
                else:
                    break
            for path in paths:
                yoko[path[0]][path[1]] = temp

for i in range(H):
    for j in range(W):
        if Ss[i][j] == "
            continue
        else:
            paths = [[i,j]]
            temp = 1
            for k in range(i+1, H):
                if Ss[k][j] == ".":
                    temp+=1
                    paths.append([k,j])
                else:
                    break
            for path in paths:
                tate[path[0]][path[1]] = temp

answer = 0
for i in range(H):
    for j in range(W):
        if answer < tate[i][j]+yoko[i][j]-1:
            answer = tate[i][j]+yoko[i][j]-1
print(answer)

Solution (Python):
h, w = map(int, input().split())
chiz = [[] for _ in range(w)]
for _ in range(h):
    tmp_list = input()
    for i in range(w):
        chiz[i].append(tmp_list[i])
rsw_w = [[0]*h for _ in range(w)]
rsw_h = [[0]*h for _ in range(w)]
for j in range(h):
    for i in range(w):
        if chiz[i][j] == '.':
            if i > 0:
                rsw_w[i][j] = rsw_w[i-1][j] + 1
            else:
                rsw_w[i][j] = 1
for j in range(h):
    for i in reversed(range(w)):
        if chiz[i][j] == '.':
            if i < w-1:
                rsw_w[i][j] = max(rsw_w[i][j],rsw_w[i+1][j])
for i in range(w):
    for j in range(h):
        if chiz[i][j] == '.':
            if j > 0:
                rsw_h[i][j] = rsw_h[i][j-1] + 1
            else:
                rsw_h[i][j] = 1
for i in range(w):
    for j in reversed(range(h)):
        if chiz[i][j] == '.':
            if j < h-1:
                rsw_h[i][j] = max(rsw_h[i][j],rsw_h[i][j+1])
res = 0
for j in range(h):
    for i in range(w):
       res = max(res,rsw_w[i][j]+rsw_h[i][j]-1)
print(res)

Solution (Python):
H,W = map(int,input().split())
S = [input().strip() for _ in range(H)]
X = [[0 for _ in range(W)] for _ in range(H)]
for i in range(H):
    j = 0
    cur = j
    while j<W:
        if S[i][j]==".":
            j += 1
        else:
            for k in range(cur,j):
                X[i][k] = j-cur
            j += 1
            cur = j
    for k in range(cur,W):
        X[i][k] = W-cur
Y = [[0 for _ in range(W)] for _ in range(H)]
for j in range(W):
    i = 0
    cur = i
    while i<H:
        if S[i][j]==".":
            i += 1
        else:
            for k in range(cur,i):
                Y[k][j] = i-cur
            i += 1
            cur = i
    for k in range(cur,H):
        Y[k][j] = H-cur
cmax = 0
for i in range(H):
    for j in range(W):
        if S[i][j]==".":
            cmax = max(cmax,X[i][j]+Y[i][j]-1)
print(cmax)

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

Solution (Python):
H, W, *SS = open(0).read().split()
H, W = int(H), int(W)

R = [[0]*(W) for _ in [0]*(H)]
C = [[0]*(W) for _ in [0]*(H)]

for i, S in enumerate(SS):
    cnt = 0
    pre = S[0]
    for j, s in enumerate(S):
        if s == '.':
            cnt += 1
        else:
            if pre == '.':
                for k in range(1, cnt+1):
                    R[i][j-k] = cnt
                cnt = 0
        pre = s
    if pre == '.':
        for k in range(1, cnt+1):
            R[i][-k] = cnt

for j in range(W):
    cnt = 0
    pre = SS[0][j]
    for i in range(H):
        s = SS[i][j]
        if s == '.':
            cnt += 1
        else:
            if pre == '.':
                for k in range(1, cnt+1):
                    C[i-k][j] = cnt
                cnt = 0
        pre = s
    if pre == '.':
        for k in range(1, cnt+1):
            C[-k][j] = cnt

ans = 0
for i in range(H):
    for j in range(W):
        if R[i][j] and C[i][j]:
            area = R[i][j]+C[i][j]-1
            if ans < area:
                ans = area
print(ans)

Solution (Python):
MOD = 10**9+7
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 j > 0:
      if S[i][j-1] == ".":
        L[i][j] = L[i][j-1]+1
      if S[i][w-j] == ".":
        R[i][w-1-j] = R[i][w-j]+1
    if i > 0:
      if S[i-1][j] == ".":
        U[i][j] = U[i-1][j]+1
      if S[h-i][j] == ".":
        D[h-1-i][j] = D[h-i][j]+1
ans = 0
for i in range(h):
  for j in range(w):
    if S[i][j] == ".":
      temp = L[i][j]+R[i][j]+U[i][j]+D[i][j]+1
      ans = max(ans, temp)
print(ans)

Solution (Python):
import numpy as np

H, W = map(int, input().split(' '))

S = np.array([[int(c == '.') for c in input()] for _ in range(H)])

up = S.copy()
down = S.copy()
left = S.copy()
right = S.copy()

for i in range(1, H):
    up[i] = (up[i - 1] + 1) * up[i]
    down[-i - 1] = (down[-i] + 1) * down[-i - 1]

for i in range(1, W):
    left[:, i] = (left[:, i - 1] + 1) * left[:, i]
    right[:, -i - 1] = (right[:, -i] + 1) * right[:, -i - 1]

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

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

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

rows = []
cols = []

for y in range(H):
    cont = 0
    row = []
    for x in range(W):
        if S[y][x] == '.':
            cont += 1
        else:
            for _ in range(cont):
                row.append(cont)
            row.append(0)
            cont = 0
    for _ in range(cont):
        row.append(cont)
    rows.append(row)

for x in range(W):
    cont = 0
    col = []
    for y in range(H):
        if S[y][x] == '.':
            cont += 1
        else:
            for _ in range(cont):
                col.append(cont)
            col.append(0)
            cont = 0
    for _ in range(cont):
        col.append(cont)
    cols.append(col)

ans = 0
for y in range(H):
    for x in range(W):
        if S[y][x] == '.':
            ans = max(ans, rows[y][x] + cols[x][y] - 1)

print(ans)

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

ans = 0
L = [[0]*w for _ in range(h)]
for hi in range(h):
    cnt = 1
    for wi in range(w):
        if S[hi][wi]=='
            L[hi][wi] = 0
            cnt = 1
        else:
            L[hi][wi] = cnt
            cnt += 1

R = [[0]*w for _ in range(h)]
for hi in range(h):
    cnt = 1
    for wi in range(w):
        if S[hi][w-wi-1]=='
            R[hi][w-wi-1] = 0
            cnt = 1
        else:
            R[hi][w-wi-1] = cnt
            cnt += 1

D = [[0]*w for _ in range(h)]
for wi in range(w):
    cnt = 1
    for hi in range(h):
        if S[hi][wi]=='
            D[hi][wi] = 0
            cnt = 1
        else:
            D[hi][wi] = cnt
            cnt += 1

U = [[0]*w for _ in range(h)]
for wi in range(w):
    cnt = 1
    for hi in range(h):
        if S[h-hi-1][wi] == '
            U[h-hi-1][wi] = 0
            cnt = 1
        else:
            U[h-hi-1][wi] = cnt
            cnt += 1

ans = 0
for hi in range(h):
    for wi in range(w):
        ans = max(ans, L[hi][wi]+R[hi][wi]+D[hi][wi]+U[hi][wi]-3)
print(ans)

Solution (Python):


import math

import itertools
from collections import deque
from collections import Counter



import bisect
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]=="
            l[i][j]=r[i][j]=u[i][j]=d[i][j]=0
        else: 
            l[i][j]=l[i][j-1]+1 if j!=0 else 1
            u[i][j]=u[i-1][j]+1 if i!=0 else 1
        if s[h-1-i][w-1-j]=="
            r[i][j]=d[i][j]=0
        else:
            r[i][j]=r[i][j-1]+1 if j!=0 else 1
            d[i][j]=d[i-1][j]+1 if i!=0 else 1
ans=0
for i in range(h):
    for j in range(w):
        res=l[i][j]+u[i][j]+r[h-1-i][w-1-j]+d[h-1-i][w-1-j]-3
        
        ans=max(res,ans)
print(ans)

Solution (Python):







__giturl__ = "$URL$"


from collections import defaultdict
from collections import deque
from collections import OrderedDict
import itertools
from sys import stdin
input = stdin.readline


def main():
  H, W = list(map(int, input().split()))
  G = ['
  G = ['

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

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

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

  print(max_ - 3)


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

Solution (Python):
import numpy as np
H ,W = map(int,input().split())

maze = [[] for _ in range(H)]
for i in range(H):
    maze[i] = np.array(list(input())) == "."
maze = np.array(maze)

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

for i in range(H):
    up[i] = (up[i-1] + 1)*maze[i]
    down[-(i+1)] = (down[-i] + 1)*maze[-(i+1)] 
    



for i in range(W):
    right[:, i] = (right[:, i-1] + 1)*maze[:, i]
    left[:, -(i+1)] = (left[:, -i] + 1)*maze[:, -(i+1)]

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

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

G = []
for _ in range(H):
    G.append(list(input()))

L, R, U, B = [], [], [], []
for y in range(H):
    targets = [L, R]
    ranges = [range(W), range(W-1, -1, -1)]
    for target, rng in zip(targets, ranges):
        row = [0] * W
        c = -1
        for x in rng:
            if G[y][x] == "
                c = -1
            else:
                c += 1
            row[x] = c
        target.append(row)
for x in range(W):
    targets = [U, B]
    ranges = [range(H), range(H-1, -1, -1)]
    for target, rng in zip(targets, ranges):
        col = [0] * H
        c = -1
        for y in rng:
            if G[y][x] == "
                c = -1
            else:
                c += 1
            col[y] = c
        target.append(col)

max_light = 0
for y in range(H):
    for x in range(W):
        light = L[y][x] + R[y][x] + U[x][y] + B[x][y] + 1
        max_light = max(light, max_light)
print(max_light)

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

def main(h,w,smat):
    tmat=[]
    for _ in range(h):
        t=[0 for tt in range(w)]
        tmat.append(t)
    
    for i in range(h):
        s=smat[i]
        l=0
        r=s.find('
        
        while(r>=0):
            for k in range(l,r):
                tmat[i][k]=r-l
            l=r+1
            if (l>=w):
                break
            r=s.find('
            
        else:
            for k in range(l,w):
                tmat[i][k]=w-l
        
    maxt=0
    for j in range(w):
        u=0
        b=u
        while b<h:
            
            while b<h and smat[b][j]=='.':
                b+=1
            for k in range(u,b):
                maxt=max(maxt, tmat[k][j]+b-u-1)
            u=b+1
            b=u

    return maxt

def main2(h,w,smat):
    l=[]
    r=[]
    u=[]
    d=[]
    for _ in range(h):
        l.append([0]*w)
        r.append([0]*w)
        u.append([0]*w)
        d.append([0]*w)

    for i in range(h):
        for j in range(w):
            if smat[i][j]=='.':
                if j==0:
                    l[i][j]=1
                else:
                    l[i][j]=l[i][j-1]+1
        for j in range(w-1,-1,-1):
            if smat[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 smat[i][j]=='.':
                if i==0:
                    u[i][j]=1
                else:
                    u[i][j]=u[i-1][j]+1
        for i in range(h-1,-1,-1):
            if smat[i][j]=='.':
                if i==h-1:
                    d[i][j]=1
                else:
                    d[i][j]=d[i+1][j]+1
    
    maxt=0
    for i in range(h):
        for j in range(w):
            maxt=max(maxt, l[i][j]+r[i][j]+u[i][j]+d[i][j]-3)
    return maxt

if __name__=='__main__':
    h,w,smat=readinput()
    ans=main2(h,w,smat)
    print(ans)

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

def main(h,w,smat):
    tmat=[]
    for _ in range(h):
        t=[0 for tt in range(w)]
        tmat.append(t)
    
    for i in range(h):
        s=smat[i]
        l=0
        r=s.find('
        
        while(r>=0):
            for k in range(l,r):
                tmat[i][k]=r-l
            l=r+1
            if (l>=w):
                break
            r=s.find('
            
        else:
            for k in range(l,w):
                tmat[i][k]=w-l
        
    maxt=0
    for j in range(w):
        u=0
        b=u
        while b<h:
            
            while b<h and smat[b][j]=='.':
                b+=1
            for k in range(u,b):
                maxt=max(maxt, tmat[k][j]+b-u-1)
            u=b+1
            b=u

    return maxt

if __name__=='__main__':
    h,w,smat=readinput()
    ans=main(h,w,smat)
    print(ans)

Solution (Python):
import numpy as np
h, w = map(int, input().split())
s = [list(input()) for i in range(h)]
li = [[0 if s[i][j] == "
l, r, u, d = np.array(li), np.array(li), np.array(li), np.array(li)
for i in range(1, h):
    u[i] *= (u[i - 1] + 1)
    d[-i - 1] *= (d[-i] + 1)
for i in range(1, w):
    l[:, i] *= (l[:, i - 1] + 1)
    r[:, -i - 1] *= (r[:, -i] + 1)
print((l + r + u + d - 3).max())

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

s = []
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):
    tmp =list(input())
    s.append(tmp)

for y in range(H):
  for x in range(W):
    if s[y][x] == "
      continue
    elif x == 0:
      l[y][x] = 1
    else:
      l[y][x] = l[y][x-1] + 1

for y in range(H):
  for x in range(W-1, -1, -1):
    if s[y][x] == "
      continue
    elif x == W - 1:
      r[y][x] = 1
    else:
      r[y][x] = r[y][x+1] + 1
      
for y in range(H):
  for x in range(W):
    if s[y][x] == "
      continue
    elif y == 0:
      u[y][x] = 1
    else:
      u[y][x] = u[y-1][x] + 1
      
for y in range(H-1, -1, -1):
  for x in range(W):
    if s[y][x] == "
      continue
    elif y == H - 1:
      d[y][x] = 1
    else:
      d[y][x] = d[y+1][x] + 1

ans = 0
for x in range(H):
  for y in range(W):
    if ans < l[x][y] + r[x][y] + u[x][y] + d[x][y] - 3:
      ans = l[x][y] + r[x][y] + u[x][y] + d[x][y] - 3
      
print(ans)

Solution (Python):
import copy

H, W = map(int, input().split())
grid = [[1 if c == "." else 0 for c in input()] for _ in range(H)]

L = copy.deepcopy(grid)
R = copy.deepcopy(grid)
U = copy.deepcopy(grid)
D = copy.deepcopy(grid)

for i in range(H):
  for j in range(1, W):
    L[i][j] = (L[i][j-1] + 1) * L[i][j]
    R[i][-1-j] = (R[i][-j] + 1) * R[i][-1-j]

for j in range(W):
  for i in range(1, H):
    U[i][j] = (U[i-1][j] + 1) * U[i][j]
    D[-1-i][j] = (D[-i][j] + 1) * D[-1-i][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] - 3, 0)

print(ans)

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

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

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

for j in range(W):
    for i in range(H):
        if S[i][j] == '
            WL[j].append(i)
ma = 0
import bisect
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            ind = bisect.bisect_left(HL[i],j)
            if ind == 0:
                left = -1
            else:
                left = HL[i][ind-1]
            if ind == len(HL[i]):
                right = W
            else:
                right = HL[i][ind]
            wid_num = right-left-1

            ind_2 = bisect.bisect_left(WL[j],i)
            if ind_2 == 0:
                up = -1
            else:
                up = WL[j][ind_2-1]
            if ind_2 == len(WL[j]):
                down = H
            else:
                down = WL[j][ind_2]
            len_num = down-up-1

            ma = max(ma,wid_num+len_num-1)
print(ma)

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

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 numpy as np

h, w = map(int, input().split())
s = np.empty((h, w), dtype='i8')
for i in range(h):
    s[i] = [i == '.' for i in list(input())]

right = np.copy(s)
left = np.copy(s)
for i in range(1, w):
    right[:, -i-1] = (right[:, -i] + 1) * s[:, -i-1]
    left[:, i] = (left[:, i-1] + 1) * s[:, i]
up = np.copy(s)
down = np.copy(s)
for i in range(1, h):
    up[i] = (up[i-1] + 1) * s[i]
    down[-i-1] = (down[-i] + 1) * s[-i-1]

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

Solution (Python):
import numpy as np


def main():
    h, w = map(int, input().split())
    s = np.array([[i == "." for i in input()] for _ in range(h)], dtype=int)
    left = s.copy()
    right = s.copy()
    up = s.copy()
    down = s.copy()
    for i in range(w - 1):
        left[:, i + 1] = (left[:, i] + 1) * s[:, i + 1]
        right[:, -i - 2] = (right[:, -i - 1] + 1) * s[:, -i - 2]
    for i in range(h - 1):
        up[i + 1] = (up[i] + 1) * s[i + 1]
        down[-i - 2] = (down[-i - 1] + 1) * s[-i - 2]
    print((left + right + up + down).max() - 3)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import numpy as np


def read():
    return sys.stdin.readline().rstrip()


def main():
    h, w = map(int, read().split())
    s = np.array([[i == "." for i in read()] for _ in range(h)], dtype=int)
    left = s.copy()
    right = s.copy()
    up = s.copy()
    down = s.copy()
    for i in range(w - 1):
        left[:, i + 1] = (left[:, i] + 1) * s[:, i + 1]
        right[:, -i - 2] = (right[:, -i - 1] + 1) * s[:, -i - 2]
    for i in range(h - 1):
        up[i + 1] = (up[i] + 1) * s[i + 1]
        down[-i - 2] = (down[-i - 1] + 1) * s[-i - 2]
    print((left + right + up + down).max() - 3)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import numpy as np


def read():
    return sys.stdin.readline().rstrip()


def main():
    h, w = map(int, read().split())
    s = np.array([[i == "." for i in read()] for _ in range(h)], dtype=int)
    left = np.zeros((h, w), dtype=int)
    right = np.zeros((h, w), dtype=int)
    up = np.zeros((h, w), dtype=int)
    down = np.zeros((h, w), dtype=int)
    left[:, 0] = s[:, 0]
    right[:, -1] = s[:, -1]
    for i in range(w - 1):
        left[:, i + 1] = (left[:, i] + 1) * s[:, i + 1]
        right[:, -i - 2] = (right[:, -i - 1] + 1) * s[:, -i - 2]
    up[0] = s[0]
    down[-1] = s[-1]
    for i in range(h - 1):
        up[i + 1] = (up[i] + 1) * s[i + 1]
        down[-i - 2] = (down[-i - 1] + 1) * s[-i - 2]
    print((left + right + up + down).max() - 3)


if __name__ == '__main__':
    main()

Solution (Python):
import sys


def read():
    return sys.stdin.readline().rstrip()


def main():
    h, w = map(int, read().split())
    s = ["
    left = [[0] * (w + 2) for _ in range(h + 2)]
    right = [[0] * (w + 2) for _ in range(h + 2)]
    up = [[0] * (w + 2) for _ in range(h + 2)]
    down = [[0] * (w + 2) for _ in range(h + 2)]
    for y in range(1, h + 1):
        for x in range(1, w + 1):
            if s[y][x] == ".":
                left[y][x] = left[y][x - 1] + 1
                up[y][x] = up[y - 1][x] + 1
            if s[-y - 1][-x - 1] == ".":
                right[-y - 1][-x - 1] = right[-y - 1][-x] + 1
                down[-y - 1][-x - 1] = down[-y][-x - 1] + 1
    c = 0
    for y in range(1, h + 1):
        for x in range(1, w + 1):
            if s[y][x] == ".":
                c = max(left[y][x] + right[y][x] + up[y][x] + down[y][x], c)
    print(c - 3)


if __name__ == '__main__':
    main()

Solution (Python):
h,w = map(int,input().split())
S = [input() for _ in range(h)]
C = [[0 for _ in range(w)] for _ in range(h)]
for i in range(h):
    new = []
    flag = False
    cnt = 0
    for j in range(w):
        if flag:
            if S[i][j] == "
                for k in new:
                    C[i][k] += cnt
                cnt = 0
                new = []
                flag = False
            else:
                cnt += 1
                new.append(j)
        else:
            if S[i][j] == ".":
                cnt = 1
                flag = True
                new.append(j)
    else:
        if flag:
            for k in new:
                C[i][k] += cnt
            cnt = 0
            flag = False
for j in range(w):
    new = []
    flag = False
    cnt = 0
    for i in range(h):
        if flag:
            if S[i][j] == "
                for k in new:
                    C[k][j] += cnt
                cnt = 0
                new = []
                flag = False
            else:
                cnt += 1
                new.append(i)
        else:
            if S[i][j] == ".":
                cnt = 1
                flag = True
                new.append(i)
    else:
        if flag:
            for k in new:
                C[k][j] += cnt
            cnt = 0
            flag = False
ans = -1
for i in range(h):
    ans = max(ans,max(C[i]))
print(ans-1)

Solution (Python):
import re
h,w = map(int, input().split())
m=[]
d = [[0]*w for _ in range(h)]
u = [[0]*w for _ in range(h)]
for _ in range(h):
  t=[]
  for i in re.split("(
    if not i == "
      t.extend([len(i)]*len(i))
    else:
      t.append(0)
  m.append(t)

for i in range(w):
  for j in range(h):
    if m[j][i] == 0:
      d[j][i] = 0
    else:
      if j != 0:
        d[j][i] = d[j-1][i] + 1
      else:
        d[j][i] = 1

    if m[h-1-j][i] == 0:
      u[h-1-j][i] = 0
    else:
      if h-1-j == h-1:
        u[h-1-j][i] = 1
      else:
        u[h-1-j][i] = u[h-j][i] + 1
ans=0
for i in range(w):
  for j in range(h):
    ans = max(ans, u[j][i]+d[j][i]+m[j][i])
print(ans - 2)

Solution (Python):


def main():
    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)]

    for i in range(H):
        for j in range(1,W):
            if S[i][j] == '.':
                if S[i][j-1] == '.': 
                    L[i][j] = L[i][j-1] + 1
            if S[i][W-j-1] == '.':
                if S[i][W-j] == '.': 
                    R[i][W-j-1] = R[i][W-j] + 1
    
    
    U = [[0]*W for _ in range(H)]
    D = [[0]*W for _ in range(H)]

    for j in range(W):
        for i in range(1,H):
            if S[i][j] == '.':
                if S[i-1][j] == '.': 
                    U[i][j] = U[i-1][j] + 1
            if S[H-i-1][j] == '.':
                if S[H-i][j] == '.': 
                    D[H-i-1][j] = D[H-i][j] + 1
    ans = 0
    
    for i in range(H):
        for j in range(W):
            tmp = 1
            tmp += L[i][j] + R[i][j] + U[i][j] + D[i][j]
            ans = max(tmp,ans)
    
    print(ans)
    
if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque, defaultdict


from collections import Counter

from itertools import accumulate,combinations,permutations

from heapq import heapify,heappop,heappush


from functools import reduce,lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    

    
    H, W = map(int, input().split())
    
    
    S = tuple(tuple(input()) for i in range(H)) 

    cnt=[[[0]*W for _ in range(H)] for _ in range(4)]
    for i in range(0,H):
        mj=-1
        for j in range(0,W):
            if S[i][j]=="
                mj=j
                continue
            cnt[0][i][j]=(j-mj-1)
    for i in range(0,H):
        mj=W
        for j in range(W-1,-1,-1):
            if S[i][j]=="
                mj=j
                continue
            cnt[1][i][j]=(mj-j-1)

    for i in range(0,W):
        mj=-1
        for j in range(0,H):
            if S[j][i]=="
                mj=j
                continue
            
            cnt[2][j][i]=(j-mj-1)
    for i in range(0,W):
        mj=H
        for j in range(H-1,-1,-1):
            if S[j][i]=="
                mj=j
                continue
            cnt[3][j][i]=(mj-j-1)
    
    ans=0
    for i in range(0,H):
        for j in range(0,W):
            if S[i][j]=="
                continue
            x=cnt[0][i][j]+cnt[1][i][j]+cnt[2][i][j]+cnt[3][i][j]+1    
            ans=max(x,ans)
    print(ans)



if __name__ == "__main__":
    main()