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



Sample input:
4 6
#..#..
.....#
....#.
#.#...


Sample output:
8

Submission status: Accepted

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

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

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

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

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

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

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

ans = 0
for i in range(h):
    for j in range(w):
        now = right[i][j]+left[i][j]+forward[i][j]+backward[i][j]-3
        ans = max(ans,now)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np


H, W = map(int, input().split())
grid = 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):
    down[i] = (down[i - 1] + 1) * grid[i]
    up[-i - 1] = (up[-i] + 1) * grid[-i - 1]

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

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

Submission status: Accepted

Solution code:
def larger(x, y):
	if x > y:
		return x
	return y

H, W = map(int, input().split())
field = []
for i in range(0, H):
	field.append(input())
upper = []
down = []
left = []
right = []
for i in range(0, H):
	lst1 = []
	lst2 = []
	lst3 = []
	lst4 = []
	for j in range(0, W):
		lst1.append(0)
		lst2.append(0)
		lst3.append(0)
		lst4.append(0)
	upper.append(lst1)
	down.append(lst2)
	left.append(lst3)
	right.append(lst4)
for i in range(0, H):
	cnt1 = 0
	cnt2 = 0
	for j in range(0, W):
		if field[i][j] == '#':
			cnt1 = 0
		else:
			left[i][j] = cnt1
			cnt1 += 1
		if field[i][-1-j] == '#':
			cnt2 = 0;
		else:
			right[i][-1-j] = cnt2
			cnt2 += 1
for i in range(0, W):
	cnt1 = 0
	cnt2 = 0
	for j in range(0, H):
		if field[j][i] == '#':
			cnt1 = 0
		else:
			upper[j][i] = cnt1
			cnt1 += 1
		if field[-1-j][i] == '#':
			cnt2 = 0
		else:
			down[-1-j][i] = cnt2
			cnt2 += 1
max = 0
for i in range(0, H):
	for j in range(0, W):
		if field[i][j] == '.':
			lamp = upper[i][j] + down[i][j] + left[i][j] + right[i][j] + 1
			max = larger(max, lamp)
print(max)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
S=[input() for i in range(H)]
A=[[0]*W for i in range(H)]
for i in range(H):
    k=0
    for j in range(W):
        if S[i][j]=="#":
            k=0
        else:
            k+=1
        A[i][j]=k
    for j in range(W-1,0,-1):
        if A[i][j-1]!=0 and A[i][j]!=0:
            A[i][j-1]=A[i][j]
B=[[0]*W for i in range(H)]
for j in range(W):
    k=0
    for i in range(H):
        if S[i][j]=="#":
            k=0
        else:
            k+=1
        B[i][j]=k
    for i in range(H-1,0,-1):
        if B[i][j]!=0 and B[i-1][j]!=0:
            B[i-1][j]=B[i][j]
ans=0
for i in range(H):
    for j in range(W):
        ans=max(ans,A[i][j]+B[i][j])
print(ans-1)

Submission status: Accepted

Solution code:
H, W = list(map(int, input().split()))
M = [['.' for w in range(W)] for h in range(H)]
for h in range(0, H):
    M[h] = list(input())

Yoko = [[0 for w in range(W)] for h in range(H)]
Tate = [[0 for w in range(W)] for h in range(H)]
for h in range(0, H):
    for w in range(0, W):
        if M[h][w] != '#':
            if w > 0 and M[h][w - 1] != '#':
                Yoko[h][w] = Yoko[h][w - 1]
            else:
                c = 0
                for d in range(w, W):
                    if M[h][d] == '#':
                        break
                    c += 1
                Yoko[h][w] = c
for w in range(0, W):
    for h in range(0, H):
        if M[h][w] != '#':
            if h > 0 and Tate[h - 1][w] > 0:
                Tate[h][w] = Tate[h - 1][w]
            else:
                c = 0
                for d in range(h, H):
                    if M[d][w] == '#':
                        break
                    c += 1
                Tate[h][w] = c
mx = 0
for w in range(0, W):
    for h in range(0, H):
        c = Yoko[h][w] + Tate[h][w] - 1
        if c > mx:
            mx = c
print(mx)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[76]:


import numpy as np
H, W = map(int, input().split())
S = np.array([list(input()) for i in range(H)])
"""
8 8
..#...#.
....#...
##......
..###..#
...#..#.
##....#.
#...#...
###.#..#
"""


# In[84]:


field = np.ones((H, W))
field[S=='#'] = 0
lm, rm, um, dm = (field.copy() for _ in [0]*4)
#print(field)
#print(lm)
#print(rm)
#print(um)
#print(dm)


# In[87]:


#np.where()
for i in range(1, H):
    um[i] = (um[i-1]+1) * field[i]
    dm[-1-i] = (dm[-i]+1) * field[-1-i]
    
for i in range(1, W):
    lm[:, i] = (lm[:, i-1]+1) * field[:, i]
    rm[:, -1-i] = (rm[:, -i]+1) * field[:, -1-i]
    #print(rm)


# In[88]:


#print(field)
#print(um)
#print(dm)
#print(lm)
#print(rm)
print(int(np.max(um+dm+lm+rm)-3))


# In[ ]:

Submission status: Accepted

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

s = [0] * H

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

# 端をゼロパディング
L = [[0 for _ in range(W+2)] for _ in range(H+2)]
R = [[0 for _ in range(W+2)] for _ in range(H+2)]
U = [[0 for _ in range(W+2)] for _ in range(H+2)]
D = [[0 for _ in range(W+2)] for _ in range(H+2)]

for i in range(1,H+1) :
    for j in range(1,W+1) :
        # 左上から
        if s[i-1][j-1] == '#' :
            L[i][j] = 0
            U[i][j] = 0
        else :
            L[i][j] = L[i][j-1] + 1
            U[i][j] = U[i-1][j] + 1
        # 右下から
        if s[-i][-j] == '#' :
            R[-i-1][-j-1] = 0
            D[-i-1][-j-1] = 0
        else :
            R[-i-1][-j-1] = R[-i-1][-j] + 1
            D[-i-1][-j-1] = D[-i][-j-1] + 1

ans = 0

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

print(ans)

Submission status: Accepted

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

seq = 0
w_bright_cell = [[0]*W for i in range(H)]
for i in range(H):
    seq = 0
    for j in range(W):
        if Ss[i][j] == "#":
            seq = 0
            w_bright_cell[i][j] = -1
            continue
        seq += 1
        w_bright_cell[i][j] = seq
    
    obstacle_flag = True
    for j in range(W-1, -1, -1):
        if w_bright_cell[i][j] == -1:
            obstacle_flag = True
            continue
        if obstacle_flag:
            obstacle_flag = False
            seq = w_bright_cell[i][j]
            continue
        w_bright_cell[i][j] = seq

seq = 0
h_bright_cell = [[0]*W for i in range(H)]
for j in range(W):
    seq = 0
    for i in range(H):
        if Ss[i][j] == "#":
            seq = 0
            h_bright_cell[i][j] = -1
            continue
        seq += 1
        h_bright_cell[i][j] = seq

    obstacle_flag = True
    for i in range(H-1, -1, -1):
        if h_bright_cell[i][j] == -1:
            obstacle_flag = True
            continue
        if obstacle_flag:
            obstacle_flag = False
            seq = h_bright_cell[i][j]
            continue
        h_bright_cell[i][j] = seq

now_max = 0
for i in range(H):
    for j in range(W):
        h = h_bright_cell[i][j]
        w = w_bright_cell[i][j]
        now_max = max((now_max, h+w))

print(now_max-1)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC129 D

H,W = list(map(int,input().split()))
Lamp = [list(input()) for _ in range(H)]
field = [[True for _ in range(W)] for _ in range(H)]

for i in range(H):
    for j in range(W):
            if Lamp[i][j] == '#':
                field[i][j] = False
L = [[1 for _ in range(W)] for _ in range(H)]
R = [[1 for _ in range(W)] for _ in range(H)]
U = [[1 for _ in range(W)] for _ in range(H)]
D = [[1 for _ in range(W)] for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if field[i][j]:
            if i-1 >= 0:
                if field[i-1][j]:
                    D[i][j] = D[i-1][j]+1
            if j-1 >= 0:
                if field[i][j-1]:
                    L[i][j] = L[i][j-1]+1
for i in range(H)[::-1]:
    for j in range(W)[::-1]:
        if field[i][j]:
            if i+1 < H:
                if field[i+1][j]:
                    U[i][j] = U[i+1][j]+1
            if j+1 < W:
                if field[i][j+1]:
                    R[i][j] = R[i][j+1]+1

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

Submission status: Accepted

Solution code:
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

H, W = nl()
grid = []
for i in range(H):
    grid.append(s())

ups = [[0]*W for j in range(H)]
downs = [[0]*W for j in range(H)]
lefts = [[0]*W for j in range(H)]
rights = [[0]*W for j in range(H)]

for col in range(W):
    p = 0
    for row in range(H):
        if grid[row][col] == '#':
            p = 0
        else:
            p += 1
        ups[row][col] = p

    p = 0
    for row in range(H-1, -1, -1):
        if grid[row][col] == '#':
            p = 0
        else:
            p += 1
        downs[row][col] = p

for row in range(H):
    p = 0
    for col in range(W):
        if grid[row][col] == '#':
            p = 0
        else:
            p += 1
        lefts[row][col] = p

    p = 0
    for col in range(W-1, -1, -1):
        if grid[row][col] == '#':
            p = 0
        else:
            p += 1
        rights[row][col] = p

res = 0
for row in range(H):
    for col in range(W):
        res = max(res, ups[row][col] + downs[row][col] + lefts[row][col] + rights[row][col] -3)
print(res)

Submission status: Accepted

Solution code:
import numpy as np

H, W = map(int, input().split())
S = np.array([list(input()) for _ in range(H)]) == '.'
T=np.zeros((H,W),dtype=int)
B=np.zeros((H,W),dtype=int)
L=np.zeros((H,W),dtype=int)
R=np.zeros((H,W),dtype=int)

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

for i in reversed(range(H-1)):
    B[i,:]=(B[i+1,:]+1)*S[i+1,:]

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

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

na=((T+B+L+R)*S).max()+1

print(na)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
s=[list(input())for _ in range(h)]
score=[[0]*w for _ in range(h)]
ans=0
range_w=range(w)
range_h=range(h)
for i in range_h:
  tmp_1=0
  tmp_2=0
  for j in range_w:
    if s[i][j]=="#":
      tmp_1=0
    else:
      tmp_1+=1
    score[i][j]+=tmp_1
    
    if s[i][-j-1]=="#":
      tmp_2=0
    else:
      tmp_2+=1
    score[i][-j-1]+=tmp_2
    
for j in range_w:
  tmp_3=0
  tmp_4=0
  for i in range_h:
    if s[i][j]=="#":
      tmp_3=0
    else:
      tmp_3+=1
    score[i][j]+=tmp_3
    
    if s[-i-1][j]=="#":
      tmp_4=0
    else:
      tmp_4+=1
    score[-i-1][j]+=tmp_4-3
for i in range(h):
  for j in range(w):
    ans=max(ans,score[i][j])
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from collections import deque
from functools import reduce
from pprint import pprint
import bisect
import copy
import fractions
import itertools
import math
import queue
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers): return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers): return reduce(LCM, numbers)
def LCM(m, n): return (m * n // fractions.gcd(m, n))


h, w = MI()
s = [IS() for _ in range(h)]
L = [[0 for _ in range(w)] for _ in range(h)]
R = [[0 for _ in range(w)] for _ in range(h)]
D = [[0 for _ in range(w)] for _ in range(h)]
U = [[0 for _ in range(w)] for _ in range(h)]

for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            L[i][j] = 0
        else:
            if j == 0:
                L[i][j] = 1
            elif j > 0:
                L[i][j] = L[i][j - 1] + 1

for i in range(h):
    for j in range(w - 1, -1, -1):
        if s[i][j] == '#':
            R[i][j] = 0
        else:
            if j == w - 1:
                R[i][j] = 1
            elif j < w - 1:
                R[i][j] = R[i][j + 1] + 1

for j in range(w):
    for i in range(h):
        if s[i][j] == '#':
            U[i][j] = 0
        else:
            if i == 0:
                U[i][j] = 1
            elif i > 0:
                U[i][j] = U[i - 1][j] + 1

for j in range(w):
    for i in range(h - 1, -1, -1):
        if s[i][j] == '#':
            D[i][j] = 0
        else:
            if i == h - 1:
                D[i][j] = 1
            elif i < h - 1:
                D[i][j] = D[i + 1][j] + 1

# pprint(L, width=40)
# pprint(R, width=40)
# pprint(U, width=40)
# pprint(D, width=40)

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

Submission status: Accepted

Solution code:
#メイン処理
H,W = map(int,input().split())
S = []
 
#二次元配列
for _ in range(H):
    a = input()
    S.append(list(a))
 
maxlamp = 0

L = [[0] * W for i in range(H)] #左
R = [[0] * W for i in range(H)] #右
D = [[0] * W for i in range(H)] #下
U = [[0] * W for i in range(H)] #上

# L = np.zeros((H,W))
# R = np.zeros((H,W))
# D = np.zeros((H,W))
# U = np.zeros((H,W))
 
#Lの計算
for _h in range(H):
    for _w in range(W):
        if S[_h][_w] != '#':
            if _w == 0:
                L[_h][_w] = 1
            elif _w > 0:
                L[_h][_w] = L[_h][_w-1] + 1
    
            if _h == 0:
                U[_h][_w] = 1
            elif _h > 0:
                U[_h][_w] = U[_h-1][_w] + 1
 
for _h in range(H-1,-1,-1):
    for _w in range(W-1,-1,-1):
        if S[_h][_w] != '#':
            if _w == W-1:
                R[_h][_w] = 1
            elif _w < W-1:
                R[_h][_w] = R[_h][_w+1] + 1
 
            if _h == H-1:
                D[_h][_w] = 1
                
            elif _h < H-1:
                D[_h][_w] = D[_h+1][_w] + 1
        
            tmp = L[_h][_w] + R[_h][_w] + U[_h][_w] + D[_h][_w] - 3
            maxlamp = max(maxlamp,tmp)
 
print(maxlamp)

Submission status: Accepted

Solution code:

import sys


# python template for atcoder1
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

H, W = map(int, input().split())
grid = [[v for v in input()[:-1]] for _ in range(H)]

col_seq = [[1]*W for _ in range(H)]
row_seq = [[1]*W for _ in range(H)]

for row in range(H):
    for col in range(W):
        if grid[row][col] == "#":
            col_seq[row][col] = 0
            row_seq[row][col] = 0

# init columns
for row in range(H):
    for col1, col2 in zip(range(W), range(1, W)):
        if grid[row][col1] == "." and grid[row][col2] == "." and col_seq[row][col1] == 1:
            seq = 2
            next_col = col2+1
            while next_col < W:
                if grid[row][next_col] == ".":
                    seq += 1
                else:
                    break
                next_col += 1
            for i in range(col1, col1+seq):
                col_seq[row][i] = seq

# init rows:
for col in range(W):
    for row1, row2 in zip(range(H), range(1, H)):
        if grid[row1][col] == "." and grid[row2][col] == "." and row_seq[row1][col] == 1:
            seq = 2
            next_row = row2+1
            while next_row < H:
                if grid[next_row][col] == ".":
                    seq += 1
                else:
                    break
                next_row += 1
            for i in range(row1, row1+seq):
                row_seq[i][col] = seq

ans = 0
for row in range(H):
    for col in range(W):
        if grid[row][col] == ".":
            tmp = col_seq[row][col]+row_seq[row][col]-1
            ans = max(ans, tmp)
print(ans)

Submission status: Accepted

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

row = [[0]*W for _ in range(H)]
column = [[0]*W for _ in range(H)]

for j in range(W):
    tmp = set()
    cnt = 0
    for i in range(H):
        if S[i][j] == "#":
            for pi,pj in tmp:
                row[pi][pj] = cnt
            tmp = set()
            cnt = 0
        else:
            tmp.add((i,j))
            cnt += 1
    for pi,pj in tmp:
        row[pi][pj] = cnt

for i in range(H):
    tmp = set()
    cnt = 0
    for j in range(W):
        if S[i][j] == "#":
            for pi,pj in tmp:
                column[pi][pj] = cnt
            tmp = set()
            cnt = 0
        else:
            tmp.add((i,j))
            cnt += 1
    for pi,pj in tmp:
        column[pi][pj] = cnt

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

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

h, w = map(int, input().split())
table = np.array([list(input()) for _ in range(h)]) == "."
D = np.zeros((h, w), dtype=int)
U = np.zeros((h, w), dtype=int)
R = np.zeros((h, w), dtype=int)
L = np.zeros((h, w), dtype=int)

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

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

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

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
S=[input() for i in range(H)]
A=[ [0]*W for i in range(H)] # extensionable size at row direction
B=[ [0]*W for i in range(H)] # extentionable size at collum direction
# make extension table
for i in range(H):
  for j in range(W):
    if S[i][j] == "#":
      A[i][j] = B[i][j] = 0
      continue
    # Calcurate extension case
    if j== 0 or A[i][j-1] == 0:
      numA = 0 # extension size of row 
      k = j
      while True:
        numA += 1
        if k == W-1 or S[i][k+1] == "#": # boundary point
          A[i][j] = numA
          break
        k += 1
    else:
      A[i][j] = A[i][j-1]
    
    if i == 0 or B[i-1][j] == 0:
      numB =0
      k = i
      while True: # extension size of cullum
        numB += 1
        if k == H-1 or S[k+1][j] == "#": # boundary point
          B[i][j] = numB
          break
        k += 1
    else:
      B[i][j] = B[i-1][j]

# max of A[i][j]+B[i][j]-1
ans = 0
for i in range(H):
  for j in range(W):
    ans = max(ans,A[i][j]+B[i][j]-1)
    #print(A[i][j]+B[i][j]-1,end=",") # for debug
  #print("")
print(ans)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
s = [input() for _ in range(h)]
 
hdots = [[0]*(w+1) for _ in range(h)]
for j in range(h):
    ndots = 0
    for i in range(1, w+1):
        if s[j][i-1] == '.':
            ndots += 1
        else:
            hdots[j][i-1] = ndots
            ndots = 0
    hdots[j][-1] = ndots if s[j][-1] == '.' else 0
    for i in range(w, 0, -1):
        if s[j][i-1] == '.':
            hdots[j][i] = ndots
        else:
            ndots = hdots[j][i-1]
vdots = [[0]*w for _ in range(h+1)]
for i in range(w):
    ndots = 0
    for j in range(1, h+1):
        if s[j-1][i] == '.':
            ndots += 1
        else:
            vdots[j-1][i] = ndots
            ndots = 0
    vdots[-1][i] = ndots if s[-1][i] == '.' else 0
    for j in range(h, 0, -1):
        if s[j-1][i] == '.':
            vdots[j][i] = ndots
        else:
            ndots = vdots[j-1][i]
 
ans = 0
for j in range(h):
    for i in range(w):
        nh, nv = hdots[j][i+1], vdots[j+1][i]
        if nh == 0 or nv == 0:
            continue
        ans = max(ans, nh+nv-1)
print(ans)

Submission status: Accepted

Solution code:
# Refered #5850116 submit
import numpy as np

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

ups = np.zeros((h, w), dtype = int)
downs = np.zeros((h, w), dtype = int)
lefts = np.zeros((h, w), dtype = int)
rights = np.zeros((h, w), dtype = int)

for i in range(1, h):
    ups[i] = (ups[i-1]+1)*s[i-1]
for i in range(h-2, -1, -1):
    downs[i] = (downs[i+1]+1)*s[i+1]
for j in range(1, w):
    lefts[:, j] = (lefts[:, j-1]+1)*s[:, j-1]
for j in range(w-2, -1, -1):
    rights[:, j] = (rights[:, j+1]+1)*s[:, j+1]
counts = ups+downs+lefts+rights
ans = np.max(counts*s)+1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
 
H,W = map(int,input().split())
S = [input() for i in range(H)]

L = [[0 for i in range(W)] for j in range(H)]
R = [[0 for i in range(W+1)] for j in range(H)]

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

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

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

Submission status: Accepted

Solution code:
#coding:utf-8
#R[i][j]:i行j列目に光を置いた時右に伸びる光の長さ
H,W = list(map(int,input().split()))
S = [0] * (H+2)
wall = ''
for _ in range(W+2):
    wall += '#'
S[0] = wall
S[H+1] = wall
for h in range(H):
    S[h+1] = '#' + input() + '#'
#print(S)
# R = [[0] * (W+2) for _ in range(H+2)]
# L = [[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)]
dp = [[0] * (W+2) for _ in range(H+2)]
start = 0
maxdp = 0
for h in range(1,H+1):
    flag = False
    for w in range(W+2):
        if S[h][w] == '#' :
            if flag == False :
                start = w
            else:
                for i in range(start+1,w):
                    dp[h][i] += w - i - 1
                    dp[h][i] += i - start - 1
                    if dp[h][i] > maxdp:
                        maxdp = dp[h][i]
                flag = False
                start = w
        else:
            flag = True
for w in range(1,W+1):
    for h in range(H+2):
        if S[h][w] == '#':
            if flag == False:
                start = h
            else:
                for i in range(start+1,h):
                    dp[i][w] += h - i - 1
                    dp[i][w] += i - start -1
                    if dp[i][w] > maxdp:
                        maxdp = dp[i][w]
                flag = False
                start = h
        else:
            flag = True
print(maxdp+1)

Submission status: Accepted

Solution code:
#coding:utf-8
#R[i][j]:i行j列目に光を置いた時右に伸びる光の長さ
H,W = list(map(int,input().split()))
S = [0] * (H+2)
wall = ''
for _ in range(W+2):
    wall += '#'
S[0] = wall
S[H+1] = wall
for h in range(H):
    S[h+1] = '#' + input() + '#'
#print(S)
# R = [[0] * (W+2) for _ in range(H+2)]
# L = [[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)]
dp = [[0] * (W+2) for _ in range(H+2)]
start = 0
maxdp = 0
for h in range(1,H+1):
    flag = False
    for w in range(W+2):
        if S[h][w] == '#' :
            if flag == False :
                start = w
            else:
                for i in range(start+1,w):
                    dp[h][i] += w - i - 1
                    dp[h][i] += i - start - 1
                    if dp[h][i] > maxdp:
                        maxdp = dp[h][i]
                    flag = False
                start = w
        else:
            flag = True
for w in range(1,W+1):
    for h in range(H+2):
        if S[h][w] == '#':
            if flag == False:
                start = h
            else:
                for i in range(start+1,h):
                    dp[i][w] += h - i - 1
                    dp[i][w] += i - start -1
                    if dp[i][w] > maxdp:
                        maxdp = dp[i][w]
                    flag = False
                start = h
        else:
            flag = True
print(maxdp+1)

Submission status: Accepted

Solution code:
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
L=[[0 for i in range(w)]for i in range(h)]
R=[[0 for i in range(w)]for i in range(h)]
D=[[0 for i in range(w)]for i in range(h)]
U=[[0 for i in range(w)]for i in range(h)]
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]=='.':
            if j==0:
                R[i][j]=1
            else:
                R[i][j]=R[i][j-1]+1

        if s[h-i-1][w-j-1]=='.':
            if j==0:
                L[h-i-1][w-j-1]=1
            else:
                L[h-i-1][w-j-1]=L[h-i-1][w-j]+1


        if s[h-i-1][w-j-1]=='.':
            if i==0:
                U[h-i-1][w-j-1]=1
            else:
                U[h-i-1][w-j-1]=U[h-i][w-j-1]+1

        if s[i][j]=='.':
            if i==0:
                D[i][j]=1
            else:
                D[i][j]=D[i-1][j]+1


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

print(ans)

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
grid = [input() for _ in range(H)]
A = [[0] * W for _ in range(H)]
B = [[0] * W for _ in range(H)]
L = [[0] * W for _ in range(H)]
R = [[0] * W for _ in range(H)]
for i in range(H):
    L[i][0] = 1 if grid[i][0] == '.' else 0
    for j in range(1, W):
        L[i][j] = L[i][j - 1] + 1 if grid[i][j] == '.' else 0
for i in range(H):
    R[i][-1] = 1 if grid[i][-1] == '.' else 0
    for j in range(W - 2, 0, -1):
        R[i][j] = R[i][j + 1] + 1 if grid[i][j] == '.' else 0
for j in range(W):
    A[0][j] = 1 if grid[0][j] == '.' else 0
    for i in range(1, H):
        A[i][j] = A[i - 1][j] + 1 if grid[i][j] == '.' else 0
for j in range(W):
    B[-1][j] = 1 if grid[-1][j] == '.' else 0
    for i in range(H - 2, -1, -1):
        B[i][j] = B[i + 1][j] + 1 if grid[i][j] == '.' else 0



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

Submission status: Accepted

Solution code:
H, W = map(int, input().split())
S = [input() for _ in range(H)]
horizontal_lights = [[0]*W for _ in range(H)]
vertical_lights = [[0]*W for _ in range(H)]

for h in range(H):
    num = 0
    s = 0
    t = 0
    while t < W:
        if S[h][t] == '#':
            for k in range(s, t):
                horizontal_lights[h][k] = num
            num = 0
            t += 1
            s = t
        else:
            t += 1
            num += 1
    for k in range(s, t):
        horizontal_lights[h][k] = num


for w in range(W):
    s = 0
    t = 0
    num = 0
    while t < H:
        if S[t][w] == '#':
            for k in range(s, t):
                vertical_lights[k][w] = num
            num = 0
            t += 1
            s = t
        else:
            t += 1
            num += 1
    for k in range(s, t):
        vertical_lights[k][w] = num

ans = 0
for h, line in enumerate(S):
    for w, c in enumerate(line):
        if c == '.':
            tmp = horizontal_lights[h][w] + vertical_lights[h][w]
            ans = max(ans, tmp-1)
print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate


def solve(string):
    h, w, *s = string.split()
    h, w = map(int, [h, w])
    t = [[1 if __s == "#" else 0 for __s in _s] for _s in s]
    hi = [list(accumulate(_t)) for _t in t]
    vi = [list(accumulate(_t)) for _t in zip(*t)]
    hg = [list(map(len, _s.split("#"))) for _s in s]
    vg = [list(map(len, "".join(_s).split("#"))) for _s in zip(*s)]
    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, hg[i][hi[i][j]] + vg[j][vi[j][i]])
    return str(ans - 1)
  
  
if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(n)])))