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
input = sys.stdin.readline

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

X = [[0]*W for _ in range(H)]
Y = [[0]*W for _ in range(H)]

for h in range(H):
    cnt = 0
    l = 0
    for w in range(W):
        if S[h][w] == '.':
            cnt += 1
        else:
            for x in range(l, w):
                X[h][x] = cnt
            l = w+1
            cnt = 0
    for x in range(l, W):
        X[h][x] = cnt

for w in range(W):
    cnt = 0
    u = 0
    for h in range(H):
        if S[h][w] == '.':
            cnt += 1
        else:
            for y in range(u, h):
                Y[y][w] = cnt
            u = h+1
            cnt = 0
    for y in range(u, H):
        Y[y][w] = cnt

ans = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == '
            continue
        ans = max(ans, X[h][w] + Y[h][w] - 1)
print(ans)

Solution (Python):
def burst(S,H,W):
    for i in range(H):
        S[i] += "d" 
    S.append("d" * (W+1))
    tate_burst = [[] for _ in range(W)]
    yoko_burst = [[] for _ in range(H)]
    
    

    for j in range(W):
        sp,ep = None,None
        for i in range(H):
            if S[i][j] == ".":
                if sp == None:
                    sp = i
                    if S[i+1][j] != ".":
                        ep = i
                        tate_burst[j].append((sp,ep))
                        sp,ep = None,None
                elif S[i+1][j] != ".":
                    ep = i
                    tate_burst[j].append((sp,ep))
                    sp,ep = None,None

    for i in range(H):
        sp,ep = None,None
        for j in range(W):
            if S[i][j] == ".":
                if sp == None:
                    sp = j
                    if S[i][j+1] != ".":
                        ep = j
                        yoko_burst[i].append((sp,ep))
                        sp,ep = None,None
                elif S[i][j+1] != ".":
                    ep = j
                    yoko_burst[i].append((sp,ep))
                    sp,ep = None,None

    return tate_burst,yoko_burst

def score(tate_burst,yoko_burst,H,W):
    T = [[-1 for _ in range(W)] for _ in range(H)]

    for j in range(W):
        for st,go in tate_burst[j]:
            for i in range(st,go+1):
                T[i][j] += (go-st+1)

    for i in range(H):
        for st,go in yoko_burst[i]:
            for j in range(st,go+1):
                T[i][j] += (go-st+1)

    return T

def max_score(T,H,W):
    output = 0
    for i in range(H):
        for j in range(W):
            output = max(output,T[i][j])

    return output

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

    B = burst(S,H,W)
    tate_burst,yoko_burst = B[0],B[1]
    T = score(B[0],B[1],H,W)
    ans = max_score(T,H,W)

    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
H, W = map(int, input().split())
S = [input() for _ in range(H)]
Ans = [[[-1, -1]for __ in range(W)] for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '
            continue
        else:
            if Ans[i-1][j][0] != -1:
                Ans[i][j][0] = Ans[i-1][j][0]
            else:
                num0 = 0
                while True:
                    num0 += 1
                    if i + num0 >= H:
                        break
                    elif S[i+num0][j] == '
                        break
                Ans[i][j][0] = num0

            if Ans[i][j-1][1] != -1:
                Ans[i][j][1] = Ans[i][j-1][1]
            else:
                num1 = 0
                while True:
                    num1 += 1
                    if j + num1 >= W:
                        break
                    elif S[i][j+num1] == '
                        break
                Ans[i][j][1] = num1

        ans = max(ans, sum(Ans[i][j]))
print(ans-1)

Solution (Python):

import sys
try:
    from typing import List
except ImportError:
    pass


def solve(H: int, W: int, S: "List[str]"):
    d = [[0] * W for _ in range(H)]
    for y in range(H):
        x = 0
        while x < W:
            while x < W and S[y][x] == "
                x += 1
            xstt = x
            while x < W and S[y][x] == ".":
                x += 1
            xend = x
            for x2 in range(xstt, xend):
                d[y][x2] += xend - xstt
    for x in range(W):
        y = 0
        while y < H:
            while y < H and S[y][x] == "
                y += 1
            ystt = y
            while y < H and S[y][x] == ".":
                y += 1
            yend = y
            for y2 in range(ystt, yend):
                d[y2][x] += yend - ystt

    print(max(max(r) for r in d) - 1)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  
    W = int(next(tokens))  
    S = [next(tokens) for _ in range(H)]  
    solve(H, W, S)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
sys.setrecursionlimit(1000000)

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

R=[[0 for i in range(w)]for i in range(h)]
L=[[0 for i in range(w)]for i in range(h)]
U=[[0 for i in range(w)]for i in range(h)]
B=[[0 for i in range(w)]for i in range(h)]

for i in range(h):
    for j in range(w):
        if maze[i][j]=="
        if j==0: L[i][j]=1
        else: L[i][j]=L[i][j-1]+1
        if i==0: U[i][j]=1
        else: U[i][j]=U[i-1][j]+1

for i in range(h):
    for j in range(w):
        if maze[h-1-i][w-1-j]=="
        if i==0:B[h-1-i][w-1-j]=1
        else: B[h-1-i][w-1-j] = B[h-i][w-1-j]+1
        if j==0:R[h-1-i][w-1-j]=1
        else: R[h-1-i][w-1-j] = R[h-1-i][w-j]+1







ma=0
for i in range(h):
    for j in range(w):
        if maze[i][j]=="
        ma=max(ma,R[i][j]+L[i][j]+U[i][j]+B[i][j]-3)

print(ma)

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

S_array = [["

def connection_check(target_list):
    connection = 0
    connection_list = list()
    
    for i in range(len(target_list)):
        if target_list[i]=="
            connection_list += [connection for _ in range(connection)]
            connection_list += [0]
            connection = 0
        elif target_list[i]==".":
            connection += 1
    
    return connection_list

W_connection_array = [[0 for _ in range(W+2)]] + [connection_check(S_array[i]) for i in range(1,H+1)] + [[0 for _ in range(W+2)]]
H_connection_array = [[0 for _ in range(H+2)]] + [connection_check([row[i] for row in S_array]) for i in range(1,W+1)] + [[0 for _ in range(H+2)]]




ans = 0

for i in range(1,H+1):
    for j in range(1,W+1):
        temp_ans = W_connection_array[i][j] + H_connection_array[j][i]
        if ans < temp_ans:
            ans = temp_ans

print(ans - 1)

Solution (Python):
import numpy as np

H, W = map(int,input().split())
S = [list(input()) for _ in range(H)]
S = np.array(S)
S = (S == '.') * 1

R = np.array([[0 for i in range(W)] for n in range(H)])
L = 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[:, 0] = S[:, 0]
        R[:, W - 1] = S[:, W - 1]
    else:
        L[:, i] = L[:, i - 1] * S[:, i] + S[:, i]
        R[:, W - i - 1] = R[:, W - i] * S[:, W - i - 1] + S[:, W - i - 1]
for i in range(H):
    if i == 0:
        U[i] = S[i]
        D[H - 1] = S[H - 1]
    else:
        U[i] = U[i - 1] * S[i] + S[i]
        D[H - i - 1] = D[H - i] * S[H - i - 1] + S[H - i - 1]

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

Solution (Python):
import numpy as np

H, W = map(int,input().split())
S = [list(str(input())) for _ in range(H)]
S = np.array(S)
S = (S == '.') * 1

R = np.zeros((H, W), dtype=int)
L = 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[:, 0] = S[:, 0]
        R[:, W - 1] = S[:, W - 1]
    else:
        L[:, i] = L[:, i - 1] * S[:, i] + S[:, i]
        R[:, W - i - 1] = R[:, W - i] * S[:, W - i - 1] + S[:, W - i - 1]
for i in range(H):
    if i == 0:
        U[i] = S[i]
        D[H - 1] = S[H - 1]
    else:
        U[i] = U[i - 1] * S[i] + S[i]
        D[H - i - 1] = D[H - i] * S[H - i - 1] + S[H - i - 1]

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

Solution (Python):
import numpy as np

H, W = map(int,input().split())
S = [list(input()) for _ in range(H)]
S = np.array(S)
S = (S == '.') * 1

R = np.zeros((H, W), dtype=int)
L = 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[:, 0] = S[:, 0]
        R[:, W - 1] = S[:, W - 1]
    else:
        L[:, i] = L[:, i - 1] * S[:, i] + S[:, i]
        R[:, W - i - 1] = R[:, W - i] * S[:, W - i - 1] + S[:, W - i - 1]
for i in range(H):
    if i == 0:
        U[i] = S[i]
        D[H - 1] = S[H - 1]
    else:
        U[i] = U[i - 1] * S[i] + S[i]
        D[H - i - 1] = D[H - i] * S[H - i - 1] + S[H - i - 1]

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

Solution (Python):
def main():
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    
    left = [[-1]*W for _ in range(H)]
    right = [[-1]*W for _ in range(H)]
    up = [[-1]*W for _ in range(H)]
    down = [[-1]*W for _ in range(H)]

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

            if S[-1-i][-1-j] == '.':
                if j == 0:
                    right[-1-i][-1-j] = 0
                else:
                    right[-1-i][-1-j] = right[-1-i][-1-(j-1)] + 1
                if i == 0:
                    down[-1-i][-1-j] = 0
                else:
                    down[-1-i][-1-j] = down[-1-(i-1)][-1-j] + 1

    ans = 0
    temp = [0] * W
    for i in range(H):
        for j in range(W):
            temp[j] = left[i][j] + right[i][j] + down[i][j] + up[i][j] + 1
        ans = max(ans, max(temp))
    print(ans)

main()

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

    left = [[-1]*W for _ in range(H)]
    right = [[-1]*W for _ in range(H)]
    up = [[-1]*W for _ in range(H)]
    down = [[-1]*W for _ in range(H)]

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

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

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

    for i in range(H):
        for j in range(W):
            if S[-1-i][-1-j] == '.':
                if i == 0:
                    down[-1-i][-1-j] = 0
                else:
                    down[-1-i][-1-j] = down[-1-(i-1)][-1-j] + 1
            
    ans = 0
    temp = [0] * W
    for i in range(H):
        for j in range(W):
            temp[j] = left[i][j] + right[i][j] + down[i][j] + up[i][j] + 1
        ans = max(ans, max(temp))
    print(ans)

main()

Solution (Python):
import numpy as np
H,W=map(int,input().split(' '))
maze = [list(input()) for i in range(H)]
maze = (np.array(maze) == '.')*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]=maze[:,i]
        R[:,W-i-1]=maze[:,W-i-1]
    else:
        L[:,i]=(L[:,i-1]+1)*maze[:,i]
        R[:,W-i-1]=(R[:,W-i]+1)*maze[:,W-i-1]
for i in range(H):
    if i==0:
        U[i,:]=maze[i,:]
        D[H-i-1,:]=maze[H-i-1,:]
    else:
        U[i,:]=(U[i-1,:]+1)*maze[i,:]
        D[H-i-1,:]=(D[H-i]+1)*maze[H-i-1,:]
print(max(np.max(U+D+L+R-3),0))

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import copy
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

h,w = [int(i) for i in input().split()]
b = [input() for i in range(h)]

ans = [[0]*w for i in range(h)]

for i in range(h):
    res = 0
    for j in range(w):
        if b[i][j] == ".":
            ans[i][j] += res
        if b[i][j] == ".":
            res += 1
        else:
            res = 0

for i in range(h):
    res = 0
    for j in range(w-1,-1,-1):
        if b[i][j] == ".":
            ans[i][j] += res
        if b[i][j] == ".":
            res += 1
        else:
            res = 0

for j in range(w):
    res = 0
    for i in range(h):
        if b[i][j] == ".":
            ans[i][j] += res
        if b[i][j] == ".":
            res += 1
        else:
            res = 0

for j in range(w):
    res = 0
    for i in range(h-1,-1,-1):
        if b[i][j] == ".":
            ans[i][j] += res
        if b[i][j] == ".":
            res += 1
        else:
            res = 0

print(max(max(row) for row in ans) + 1)

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


row = [[0] * w for _ in range(h)]
col = [[0] * w for _ in range(h)]
for i in range(h):
    prev_wall = -1
    for j in range(w + 1):
        if j == w:
            for k in range(prev_wall+1, j):
                row[i][k] = j - prev_wall - 1
        elif s[i][j] == '
            for k in range(prev_wall+1, j):
                row[i][k] = j - prev_wall - 1
            prev_wall = j

for j in range(w):
    prev_wall = -1
    for i in range(h + 1):
        if i == h:
            for k in range(prev_wall+1, i):
                col[k][j] = i - prev_wall - 1
        elif s[i][j] == '
            for k in range(prev_wall+1, i):
                col[k][j] = i - prev_wall - 1
            prev_wall = i


ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, row[i][j] + col[i][j] - 1)
print(ans)

Solution (Python):
h,w = map(int,input().split()) 
s = [0 for i in range(h)]
s1 = [[-1 for i in range(w)]for j in range(h)]
s2 = [[-1 for i in range(w)]for j in range(h)]
ans = 0
for i in range(h):
    s[i] = list(input())
for i in range(h):
    p = 0
    d = [-1]
    for j in range(w):
        if s[i][j] == '
            d.append(j)
    d.append(w)
    for j in range(w):
        if s[i][j] == '.':
            s1[i][j] = d[p+1]-d[p]-1
        else:
            p += 1
for j in range(w):
    p = 0
    d = [-1]
    for i in range(h):
        if s[i][j] == '
            d.append(i)
    d.append(h)
    for i in range(h):
        if s[i][j] == '.':
            s2[i][j] = d[p+1]-d[p]-1
        else:
            p += 1       
for i in range(h):
    for j in range(w):
        ans =  max(ans,s1[i][j] + s2[i][j])

        
        
print(ans-1)

Solution (Python):
import sys


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


MOD = 998244353


def main():
    H, W = map(int, input().split())
    S = [input() for _ in range(H)]
    height = [[0] * W for _ in range(H)]
    width = [[0] * W for _ in range(H)]

    for h in range(H):
        cnt = 0
        for w in range(W):
            if S[h][w] == ".":
                cnt += 1
            else:
                width[h][w - cnt : w] = [cnt] * cnt
                cnt = 0
        width[h][W - cnt : W] = [cnt] * cnt
    for w in range(W):
        cnt = 0
        for h in range(H):
            if S[h][w] == ".":
                cnt += 1
            else:
                for i in range(cnt):
                    height[h - cnt + i][w] = cnt
                cnt = 0
        for i in range(cnt):
            height[H - cnt + i][w] = cnt
    answer = 0
    for h in range(H):
        for w in range(W):
            ans = width[h][w] + height[h][w] - 1
            if ans > answer:
                answer = ans
    print(answer)


if __name__ == "__main__":
    main()

Solution (Python):
h, w = list(map(int, input().split()))
s = [list(map(str, list(input()))) for i in range(h)]  
yoko = [[] for _ in range(h)]
tate = [[] for _ in range(w)]
for i in range(h):
    cnt = 0
    for j in range(w):
        if j == w-1:
            if s[i][j] == '.':
                cnt += 1
                yoko[i] += [cnt] * (cnt)
            else:
                yoko[i] += [cnt] * (cnt)
                yoko[i].append(0)
        else:
            if s[i][j] == '.':
                cnt += 1
            else:
                yoko[i] += [cnt] * (cnt)
                yoko[i].append(0)
                cnt = 0

for i in range(w):
    cnt = 0
    for j in range(h):
        if j == h-1:
            if s[j][i] == '.':
                cnt += 1
                tate[i] += [cnt] * (cnt)
            else:
                tate[i] += [cnt] * (cnt)
                tate[i].append(0)
        else:
            if s[j][i] == '.':
                cnt += 1
            else:
                tate[i] += [cnt] * (cnt)
                tate[i].append(0)
                cnt = 0

ans = -1
for i in range(h):
    for j in range(w):
        ans = max(ans, yoko[i][j]+tate[j][i]-1)
print(ans)

Solution (Python):

from copy import deepcopy
def main():
    h, w = map(int, input().split())
    matrix = []
    for _ in range(h):
        row = list(input())
        matrix.append(row)

    left = [[0] * w for _ in range(h)] 
    right = [[0] * w for _ in range(h)] 
    up = [[0] * w for _ in range(h)] 
    down = [[0] * w for _ in range(h)] 

    for i in range(h):
        c = 0
        for j in range(w):
            if matrix[i][j] == '.':
                c += 1
            else:
                c = 0
            left[i][j] = c
    for i in range(h):
        c = 0
        for j in range(w)[::-1]:
            if matrix[i][j] == '.':
                c += 1
            else:
                c = 0
            right[i][j] = c
    for j in range(w):
        c = 0
        for i in range(h):
            if matrix[i][j] == '.':
                c += 1
            else:
                c = 0
            up[i][j] = c
    for j in range(w):
        c = 0
        for i in range(h)[::-1]:
            if matrix[i][j] == '.':
                c += 1
            else:
                c = 0
            down[i][j] = c
    ans = 1
    for i in range(h):
        for j in range(w):
            t = left[i][j] + right[i][j] + up[i][j] + down[i][j] - 3
            ans = max(ans, t)
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
def main():
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    left = [[0] * W for _ in range(H)]
    right = [[0] * W for _ in range(H)]
    up = [[0] * W for _ in range(H)]
    down = [[0] * W for _ in range(H)]
    for i in range(H):
        cnt = 0
        for j in range(W):
            if S[i][j] == '
                cnt = 0
            else:
                cnt += 1
            left[i][j] = cnt
    
    for i in range(H):
        cnt = 0
        for j in range(W-1,-1,-1):
            if S[i][j] == '
                cnt = 0
            else:
                cnt += 1
            right[i][j] = cnt
    
    for j in range(W):
        cnt = 0
        for i in range(H):
            if S[i][j] == '
                cnt = 0
            else:
                cnt += 1
            up[i][j] = cnt
    
    for j in range(W):
        cnt = 0
        for i in range(H-1,-1,-1):
            if S[i][j] == '
                cnt = 0
            else:
                cnt += 1
            down[i][j] = cnt
    
    ans = 0
    for i in range(H):
        for j in range(W):
            tmp = up[i][j] + down[i][j] + left[i][j] + right[i][j] - 3
            ans = max(ans, tmp)


    print(ans)
    


if __name__ == "__main__":
    main()

Solution (Python):
H,W = map(int,input().split())
maze = []
for i in range(H):
  s = input()
  maze.append(s)
def distance(maze,H,W):
  wall = []
  for i in range(H):
    w = [-1]
    for j in range(W):
      if maze[i][j] == '
        w.append(j)
    w.append(W)
    wall.append(w)

  wd = [[0]*W for _ in range(H)]
  for i in range(H):
    w1 = 0
    for j in range(W):
      if maze[i][j] == '
        w1 = min(w1+1,len(wall[i])-1)
        continue
      wd[i][j] = j-wall[i][w1]-1+wall[i][w1+1]-j-1

  return wd

wd = distance(maze,H,W)
maze = [list(x) for x in zip(*maze)]
hd = distance(maze,W,H)
max_dist = 1

for i in range(H):
  for j in range(W):
    max_dist = max(max_dist,wd[i][j] + hd[j][i]+1)
print(max_dist)

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

for i in range(H):
    done = [0] * W
    for j in range(W):
        if S[i][j] == '
            continue
        if done[j]:
            continue
        l = 0
        while j + l < W:
            if S[i][j+l] == '
                break
            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 S[i][j] == '
            continue
        if done[i]:
            continue
        l = 0
        while i + l < H:
            if S[i+l][j] == '
                break
            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):
def main():
    H, W = (int(_) for _ in input().split())
    S = [input() for _ in range(H)]
    yoko = [[0] * W for _ in range(H)]
    tate = [[0] * W for _ in range(H)]

    for i in range(H):
        right = 0
        cc = 0
        for left in range(W):
            if S[i][left] == '
                cc = 0
                right += 1
                continue
            while right < W and S[i][right] == '.':
                right += 1
            cc = right - left
            if left > 0 and S[i][left-1] == '.': yoko[i][left] = yoko[i][left-1]
            else: yoko[i][left] = cc
    for i in range(W):
        bottom = 0
        cc = 0
        for top in range(H):
            if S[top][i] == '
                cc = 0
                bottom += 1
                continue
            while bottom < H and S[bottom][i] == '.':
                bottom += 1
            cc = bottom - top
            if top > 0 and S[top-1][i] == '.': tate[top][i] = tate[top-1][i]
            else: tate[top][i] = cc
    output = 0
    for i in range(H):
        for j in range(W):
            output = max(output, yoko[i][j]+tate[i][j]-1)
    print(output)
    return

if __name__ == '__main__':
    main()

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

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

for i in range(h):
    done=[0] * w

    for j in range(w):
        if s[i][j] == '
        if done[j] :continue

        l = 0
        while j+l < w:
            if s[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 s[i][j] == '
        if done[i] :continue

        l = 0
        while i+l < h:
            if s[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):


import numpy as np

def main():
    H,W = map(int,input().split())
    S = np.array([list(input()) for _ in range(H)]) == '.' 

    up = np.zeros((H,W), dtype=int)
    down = np.zeros((H,W), dtype=int)
    left = np.zeros((H,W), dtype=int)
    right = np.zeros((H,W), dtype=int)
    
    for i in range(H-1):
        up[i+1,:] = (up[i,:] + 1) * S[i,:] 
    for i in range(H-1):                   
        down[H - 2 - i,:] = (down[H - 1 - i,:] + 1) * S[H - 1 - i,:]
    for i in range(W-1):
        left[:,i+1] = (left[:,i] + 1) * S[:,i]
    for i in range(W-1):
        right[:,W - 2 - i] = (right[:,W - 1 - i] + 1) * S[:,W - 1 - i]
        
    print(((up+down+left+right)*S).max()+1) 
    
if __name__ == "__main__":
    main()

Solution (Python):
H, W = map(int, input().split())
S = [[c == "." for c in input()] for _ in range(H)]
to_right = [[0] * W for _ in range(H)]
to_left = [[0] * W for _ in range(H)]
for i in range(H):
    right = 0
    left = 0
    for j in range(W):
        if S[i][j]:
            right += 1
        else:
            right = 0
        to_right[i][j] = right
        if S[i][-(j + 1)]:
            left += 1
        else:
            left = 0
        to_left[i][-(j + 1)] = left
to_bottom = [[0] * W for _ in range(H)]
to_top = [[0] * W for _ in range(H)]
for j in range(W):
    bottom = 0
    top = 0
    for i in range(H):
        if S[i][j]:
            bottom += 1
        else:
            bottom = 0
        to_bottom[i][j] = bottom
        if S[-(i + 1)][j]:
            top += 1
        else:
            top = 0
        to_top[-(i + 1)][j] = top
ans = 0
for i in range(H):
    right = 0
    left = 0
    for j in range(W):
        if not S[i][j]:
            continue
        ans = max(ans, sum((to_right[i][j], to_left[i][j], to_bottom[i][j], to_top[i][j])))
print(ans - 3)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
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)]
    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]=0
                U[i][j]=0
                continue
            if i==0:U[i][j]=1
            else:U[i][j]=U[i-1][j]+1
            if j==0:L[i][j]=1
            else:L[i][j]=L[i][j-1]+1
    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
                continue
            if i==h-1:D[i][j]=1
            else:D[i][j]=D[i+1][j]+1
            if j==w-1:R[i][j]=1
            else:R[i][j]=R[i][j+1]+1 
    X=[[l+r+u+d-3 for l,r,u,d in zip(ll,rr,uu,dd)] for ll,rr,uu,dd in zip(L,R,U,D)]
    print(max([max(x) for x in X]))


if __name__=='__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
 
h,w=map(int,input().split())
s=list(input() for _ in range(h))
 
yoko=[[0]*w for _ in range(h)]
tate=[[0]*w for _ in range(h)]
 
def yoko_check(y,x,cnt):
    global yoko,s
    if x==w-1:
        yoko[y][x]=cnt
        return cnt
    else:
        if s[y][x+1]=="
            yoko[y][x]=cnt
            return cnt
        else:
            yoko[y][x]=yoko_check(y,x+1,cnt+1)
            return yoko[y][x]
 
 
def tate_check(y,x,cnt):
    global tate,s
    if y==h-1:
        tate[y][x]=cnt
        return cnt
    else:
        if s[y+1][x]=="
            tate[y][x]=cnt
            return cnt
        else:
            tate[y][x]=tate_check(y+1,x,cnt+1)
            return tate[y][x]
 
 
for y in range(h):
    for x in range(w):
        if yoko[y][x]==0 and s[y][x]==".":
            yoko_check(y,x,1)
        if tate[y][x]==0 and s[y][x]==".":
            tate_check(y,x,1)
 

 
result=0
for y in range(h):
    for x in range(w):
        if s[y][x]==".":
            result=max(result,tate[y][x]+yoko[y][x]-1)  
 
print(result)

Solution (Python):


import numpy as np

H, W = map(int, input().split())
M = [list(input()) for _ in range(H)]
M = (np.array(M) == '.') * 1

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

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

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

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