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:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

H,W = map(int, readline().split())
grid = np.frombuffer(read(), 'S1').reshape(H,-1)[:,:W]

X,Y = np.where(grid == b'#')

A = np.ones((H,W), np.int32)
B = np.ones((H,W), np.int32)

A[X,Y] = 0
B[X,Y] = 0

for w in range(W-1):
	A[:,w+1] += A[:,w] * (A[:,w+1] != 0)
for w in range(W-2,-1,-1):
	A[:,w] = np.maximum(A[:,w], A[:,w+1]) * (A[:,w] != 0)


for h in range(H-1):
	B[h+1,:] += B[h,:] * (B[h+1,:] != 0)
for h in range(H-2,-1,-1):
	B[h,:] = np.maximum(B[h,:], B[h+1,:]) * (B[h,:] != 0)

C = A+B

print(np.max(C)-1)

Submission status: Accepted

Solution code:
import numpy as np

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

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(h):
    D[i] = (D[i-1]+1) * s[i]
    U[-i-1] = (U[-i]+1) * s[-i-1]

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


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

Submission status: Accepted

Solution code:
import copy


def make_empty_nums():
    under_empty_nums = [[0 for _ in range(W)] for _ in range(H)]

    for h in range(H - 1, -1, -1):
        for w in range(W):
            if grids[h][w] == '#':
                under_empty_nums[h][w] = 0
            else:
                if h == H - 1:
                    under_empty_nums[h][w] = 1
                else:
                    under_empty_nums[h][w] = under_empty_nums[h + 1][w] + 1

    empty_nums = copy.copy(under_empty_nums)
    for h in range(1, H):
        for w in range(W):
            if empty_nums[h][w] != 0:
                empty_nums[h][w] = max(empty_nums[h][w], empty_nums[h-1][w])

    return empty_nums


H, W = map(int, input().split())
grids = [input() for _ in range(H)]
empty_nums = make_empty_nums()
ans = 0
for h in range(H):
    max_lighted_grids = 0
    tmp_max_lighted_grids = [0, 0]
    for w in range(W):
        if empty_nums[h][w] == 0:
            max_lighted_grids = max(max_lighted_grids, sum(tmp_max_lighted_grids) - 1)
            tmp_max_lighted_grids = [0, 0]
        else:
            tmp_max_lighted_grids[0] = max(tmp_max_lighted_grids[0], empty_nums[h][w])
            tmp_max_lighted_grids[1] += 1
            if w == W-1:
                max_lighted_grids = max(max_lighted_grids, sum(tmp_max_lighted_grids) - 1)
    ans = max(ans, max_lighted_grids)
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import numpy as np

### TESTCASE
test = ""
#test = \
"""
4 6
#..#..
.....#
....#.
#.#...
ans 8
"""

"""
8 8
..#...#.
....#...
##......
..###..#
...#..#.
##....#.
#...#...
###.#..#
ans 13
"""
############
test = list(reversed(test.strip().splitlines()))
if test:
    def input2():
        return test.pop()
else:
    def input2():
        return input()
####### MAIN

h, w = map(int, input2().split())
s = [["#"] * (w+1)]
s += [list("#" + input2()) for _ in range(h)]
s = np.array(s)

hs = np.zeros((h+1, w+1), dtype="int64")
ws = np.zeros((h+1, w+1), dtype="int64")

for hi in range(1, h+1):
    htmp = np.array(s[hi] == ".", dtype="int")
    hs[hi] = hs[hi-1] * htmp + htmp
    
for hj in range(h-1, 0, -1):
    hs[hj] = np.maximum(hs[hj], np.minimum(hs[hj+1], hs[hj] * hs[hj+1]))
    
for wi in range(1, w+1):
    wtmp = np.array(s[:, wi] == ".", dtype="int")
    ws[:, wi] = ws[:, wi-1] * wtmp + wtmp
    
for wj in range(w-1, 0, -1):
    ws[:, wj] = np.maximum(ws[:, wj], 
      np.minimum(ws[:, wj+1], ws[:, wj] * ws[:, wj+1]))
    
print(np.max(ws + hs) - 1)

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
S = [input().strip() for _ in range(H)]
L = [[0 for _ in range(W)] for _ in range(H)]
R = [[0 for _ in range(W)] for _ in range(H)]
U = [[0 for _ in range(W)] for _ in range(H)]
D = [[0 for _ in range(W)] for _ in range(H)]
for i in range(H):
    for j in range(W):
        if j==0 and S[i][j]==".":
            L[i][j] = 1
        elif j>0 and S[i][j]==".":
            L[i][j] = L[i][j-1]+1
        if i==0 and S[i][j]==".":
            U[i][j] = 1
        elif i>0 and S[i][j]==".":
            U[i][j] = U[i-1][j]+1
for i in range(H-1,-1,-1):
    for j in range(W-1,-1,-1):
        if j==W-1 and S[i][j]==".":
            R[i][j] = 1
        elif j<W-1 and S[i][j]==".":
            R[i][j] = R[i][j+1]+1
        if i==H-1 and S[i][j]==".":
            D[i][j] = 1
        elif i>0 and S[i][j]==".":
            D[i][j] = D[i+1][j]+1
cmax = 0
for i in range(H):
    for j in range(W):
        cmax = max(cmax,L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)
print(cmax)

Submission status: Accepted

Solution code:
H,W =map(int,input().split())
S=[[] for _ in range(H+2)]
for i in range(H):
    S[i+1]="#"+input()+"#"
S[0]="#"*(W+2)
S[-1]="#"*(W+2)

hori=[[0]*(W+2) for _ in range(H+2)]
ver=[[0]*(W+2) for _ in range(H+2)]


def count(i,j):
    if hori[i][j-1]==0:
        count=0
        for k in range(W):
            if S[i][j+k]==".":
                count+=1
            else:
                break
        hori[i][j]=count
    else:
        hori[i][j]=hori[i][j-1]
        
    if ver[i-1][j]==0:
        count=0
        for k in range(H):
            if S[i+k][j]==".":
                count+=1
            else:
                break
        ver[i][j]=count
    else:
        ver[i][j]=ver[i-1][j]
    return hori[i][j]+ver[i][j]-1
    
ans=0
for i in range(1,H+1):
    for j in range(1,W+1):
        if S[i][j]==".":
            ans=max(ans,count(i,j))
print(ans)

Submission status: Accepted

Solution code:
#import sys
#input = sys.stdin.buffer.readline
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[-i-2,:] = (down[-i-1,:] + 1) * S[-i-1,:]
    for i in range(W-1):
        left[:,i+1] = (left[:,i] + 1) * S[:,i]
    for i in range(W-1):
        right[:,-i-2] = (right[:,-i-1] + 1) * S[:,-i-1]
        
    print(((up+down+left+right)*S).max()+1)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
s=[input() for i in range(H)]
yoko=[[0 for i in range(W)] for m in range(H)]
tate=[[0 for i in range(W)] for m in range(H)]

for h in range(H):
    count=0
    for w in range(W):
        if s[h][w]=="#":
            count=0
        else:
            count+=1
        yoko[h][w]=count
    for w in range(W-2,-1,-1):
        if s[h][w]=="." and s[h][w+1]==".":
            yoko[h][w]=yoko[h][w+1]

for w in range(W):
    count=0
    for h in range(H):
        if s[h][w]=="#":
            count=0
        else:
            count+=1
        tate[h][w]=count
    for h in range(H-2,-1,-1):
        if s[h][w]=="." and s[h+1][w]==".":
            tate[h][w]=tate[h+1][w]

lst=[]
for h in range(H):
    for w in range(W):
        lst.append(tate[h][w]+yoko[h][w]-1)
print(max(lst))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np


h, w = map(int, input().split())

GRID = []
for _ in range(h):
    S = [0] + [0 if c == "#" else 1 for c in input().strip()] + [0]
    GRID.append(S)
GRID.insert(0, [0] * (w + 2))
GRID.append([0] * (w + 2))
grid = np.array(GRID)

top = np.zeros((h + 2, w + 2), dtype = np.int)
bottom = np.zeros((h + 2, w + 2), dtype = np.int)
left = np.zeros((h + 2, w + 2), dtype = np.int)
right = np.zeros((h + 2, w + 2), dtype = np.int)

for i in range(1, h + 1):
    top[i] = (top[i - 1] + 1) * grid[i]
for i in range(h, 0, -1):
    bottom[i] = (bottom[i + 1] + 1) * grid[i]
for j in range(1, w + 1):
    left[:, j] = (left[:, j - 1] + 1) * grid[:, j]
for j in range(w, 0, -1):
    right[:, j] = (right[:, j + 1] + 1) * grid[:, j]

column = (top + bottom - 1) * grid
row = (left + right - 1) * grid
lighted = (column + row - 1) * grid

ans = lighted.max()
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
H, W = map(int,input().split())
S = [ str(input()) for i in range(H) ]
sumlist = []
for i in range(H):
    tmp = 0
    for j in range(W):
        if S[i][j] == '#':
            for k in range(tmp):
                sumlist.append(tmp)
            sumlist.append(0)
            tmp = 0
            continue
        else:
            tmp += 1
    for k in range(tmp):
        sumlist.append(tmp)
sumlist2 = []
for i in range(W):
    tmp = 0
    for j in range(H):
        if S[j][i] == '#':
            for k in range(tmp):
                sumlist2.append(tmp)
            sumlist2.append(0)
            tmp = 0
            continue
        else:
            tmp += 1
    for k in range(tmp):
        sumlist2.append(tmp)
res = [sumlist[i]+sumlist2[(i%W)*H+(i//W)] for i in range(H*W)]
print(max(res)-1)

Submission status: Accepted

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

L = [[0] * (W + 1) for _ in range(H + 1)]
R = [[0] * (W + 1) for _ in range(H + 1)]
A = [[0] * (W + 1) for _ in range(H + 1)]
B = [[0] * (W + 1) for _ in range(H + 1)]

for h in range(H):
    for w in range(W):
        if grid[h][w] == '.':
            L[h][w + 1] = L[h][w] + 1
            A[h + 1][w] = A[h][w] + 1

        hh = H - 1 - h
        ww = W - 1 - w
        if grid[hh][ww] == '.':
            B[hh - 1][ww] = B[hh][ww] + 1
            R[hh][ww - 1] = R[hh][ww] + 1

ans = 0
for h in range(H):
    for w in range(W):
        if grid[h][w] == '.':
            ans = max(ans, L[h][w] + R[h][w] + A[h][w] + B[h][w] + 1)
print(ans)

Submission status: Accepted

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

light = [0] * 4 * (W + 1) * (H + 1)

row = 4 * (W + 1)
col = 4

for h in range(H):
    for w in range(W):
        if grid[h][w] == '.':
            here = row * h + col * w
            light[row * (h + 1) + col * w + 1] = light[here + 1] + 1
            light[row * h + col * (w + 1) + 3] = light[here + 3] + 1

ans = 0
for h in range(H - 1, -1, -1):
    for w in range(W - 1, -1, -1):
        if grid[h][w] == '.':
            here = row * h + col * w
            light[row * (h - 1) + col * w + 0] = light[here + 0] + 1
            light[row * h + col * (w - 1) + 2] = light[here + 2] + 1
            ans = max(ans, sum(light[here: here + 4]) + 1)

print(ans)

Submission status: Accepted

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

c = [[0 for w in range(W)] for h in range(H)]

hs = [0 for i in range(W)]

for h in range(H):
    ws = 0
    for w in range(W):
        if g[h][w] == '#':
            for i in range(ws,w):
                c[h][i] += w-ws-1
            ws = w+1
            for j in range(hs[w],h):
                c[j][w] += h-hs[w]
            hs[w] = h+1
    w2 = w+1
    for i in range(ws,w2):
        c[h][i] += w2-ws-1
h2 = h+1
for w in range(W):
    for j in range(hs[w],h2):
        c[j][w] += h2-hs[w]

#print(c)

ans = 0
for h in range(H):
    for w in range(W):
        ans = max(ans,c[h][w])

print(ans)
'''
横方向と縦方向に分けてプログラムを作成してまとめた
横方向
for h in range(H):
    ws = 0
    for w in range(W):
        if g[h][w] == '#':
            for i in range(ws,w):
                c[h][i] += w-ws-1
            ws = w+1
    w2 = w+1
    for i in range(ws,w2):
        c[h][i] += w2-ws-1

縦方向
hs = [0 for i in range(W)]
for h in range(H):
    for w in range(W):
        if g[h][w] == '#':
            for j in range(hs[w],h):
                c[j][w] += h-hs[w]
            hs[w] = h+1
h2 = h+1
for w in range(W):
    for j in range(hs[w],h2):
        c[j][w] += h2-hs[w]
'''

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())
import sys
input = sys.stdin.readline
def sc(s):
    b = None
    nc = 0
    kk = [0]*len(s)
    for i, c in enumerate(s):
        if c == ".":
            if c == b:
                nc += 1
            else:
                si = i
        else:
            if b == ".":
                for j in range(si, i):
                    kk[j] = i - si
            nc = 0
        b = c
    return kk
d = []
d2 = []
d3 = []
for h in range(H):
    s = input().strip()
    d.append(s)
    d2.append(sc(s+"#"))

d = list(zip(*d))
for s in d:
    d3.append(sc("".join(s)+"#"))
r = 0
for i in range(H):
    for j in range(W):
        r = max(r, d2[i][j] + d3[j][i]-1)
print(r)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  s=[S() 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
        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]:
    for j in range(w)[::-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

  ans=0
  # print(R,L,D,U)
  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)

  return ans

# main()
print(main())

Submission status: Accepted

Solution code:
import math
import heapq
import bisect
import numpy as np


h,w = map(int, input().split())
M = 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) * M[i]
    D[-i-1] = (D[-i] + 1) * M[-i-1]

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

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

Submission status: Accepted

Solution code:
def main():
    H, W = map(int, raw_input().split())
    G = [list(raw_input()) for i in range(H)]


    up = [[0] * W for i in range(H)]  # あるマスから上に連続していくつ障害物のないマスが続くか
    right = [[0] * W for i in range(H)]  # あるマスから右に連続していくつ障害物のないマスが続くか
    down = [[0] * W for i in range(H)]  # あるマスから下に連続していくつ障害物のないマスが続くか
    left = [[0] * W for i in range(H)]  # あるマスから左に連続していくつ障害物のないマスが続くか


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

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

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

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


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

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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


U = [[0]*(W+1) for h in range(H+1)]
L = [[0]*(W+1) for h in range(H+1)]
for h in range(H):
  for w in range(W):
    if S[h][w] == '#':
      continue
    
    U[h+1][w+1] = U[h][w+1] + 1
    L[h+1][w+1] = L[h+1][w] + 1


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

    D[h][w] = D[h+1][w] + 1
    R[h][w] = R[h][w+1] + 1
    ans = max(ans, D[h][w]+R[h][w]+U[h+1][w+1]+L[h+1][w+1]-3)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

S = np.ones([H+2, W+2], dtype=bool)
for h in range(H):
  S[h+1] = np.array(['.'] + list(input()) + ['.']) == '.'

dp1 = np.zeros([H+2, W+2, 2], dtype=int) # [up, left]
for h in range(H):
  dp1[h+1, :, 0] = (dp1[h, :, 0] + 1)*S[h+1]

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

dp2 = np.zeros([H+2, W+2, 2], dtype=int) # [down, right]
for h in range(H, 0, -1):
  dp2[h, :, 0] = (dp2[h+1, :, 0] + 1)*S[h]

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

print(np.max((np.sum(dp1, axis=2)+np.sum(dp2, axis=2))[1:-1, 1:-1])-3)

Submission status: Accepted

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
#from scipy.misc import comb

MOD = 10**9+7

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

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

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

Submission status: Accepted

Solution code:
# 2019/12/27

h,w=map(int,input().split())
s=[list('#'*(w+2))]
for _ in range(h):
    s+=[list('#'+input()+'#')]
s+=[list('#'*(w+2))]

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


for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j]=="#":continue
        L[i][j]=L[i][j-1]+1
        U[i][j]=U[i-1][j]+1

ans=0

for i in range(h,0,-1):
    for j in range(w,0,-1):
        if s[i][j]=="#":continue
        R[i][j]=R[i][j+1]+1
        D[i][j]=D[i+1][j]+1
        lit=L[i][j]+U[i][j]+R[i][j]+D[i][j]-3
        ans=max(ans,lit)
print(ans)

Submission status: Accepted

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

lst2 = [[0 for j in range(w)] for i in range(h)]

def search_of_height_branch(i,j):
    height = 0
    while True:
        if i >= h or lst1[i][j] == "#":
            break
        height += 1
        i += 1
    return height
        
def search_of_width_branch(i,j):
    width = 0
    while True:
        if j >= w or lst1[i][j] == "#":
            break
        width += 1
        j += 1
    return width

def search_of_height():
    flag = 0
    for i in range(w):
        flag = 0
        for j in range(h):
            if lst1[j][i] == "." and flag==0:
                point = search_of_height_branch(j,i)
                lst2[j][i] += point
                flag = 1
            elif lst1[j][i] == ".":
                lst2[j][i] += point
            else:
                flag = 0

def search_of_width():
    flag = 0
    for i in range(h):
        flag = 0
        for j in range(w):
            if lst1[i][j] == "." and flag==0:
                point = search_of_width_branch(i,j)
                lst2[i][j] += point
                flag = 1
            elif lst1[i][j] == ".":
                lst2[i][j] += point
            else:
                flag = 0

if __name__ == "__main__":
    search_of_height()
    search_of_width()
    ans = 0
    for i in range(h):
        ans = max(ans,max(lst2[i]))
    print(ans-1) #交差している点が重複して数えているので-1

Submission status: Accepted

Solution code:
import sys

H,W = map(int,input().split())
grids = [[s for s in sys.stdin.readline()] for _ in range(H)]

col_cnt = [[0 for _ in range(W)]for _ in range(H)]
for i in range(W):
  tmp_cnt = 0
  prvjj = 0
  for j in range(H):
    if grids[j][i] == '.':
      tmp_cnt += 1
    else:
      col_cnt[j][i] = 0
      for jj in range(prvjj,j):
        col_cnt[jj][i] = tmp_cnt
      prvjj = j+1
      tmp_cnt = 0
  for jj in range(prvjj,H):
    col_cnt[jj][i] = tmp_cnt

ans = -float('inf')
for j in range(H):
  tmp_cnt = 0
  prvii = 0
  for i in range(W):
    if grids[j][i] == '.':
      tmp_cnt += 1
    else:
      for ii in range(prvii,i):
        ans = max(ans,col_cnt[j][ii]+tmp_cnt-1)
      prvii = i+1
      tmp_cnt = 0

  for ii in range(prvii,W):
    ans = max(ans,col_cnt[j][ii]+tmp_cnt-1)

print(ans)

Submission status: Accepted

Solution code:
# これ愚直じゃダメなのかな
# 上下左右それぞれのテーブルを用意し、いまいるところより上/下/左/右にいくつあるかをセーブする（自分は含まない）
# ↑ この4方向累積和方針はあってるっぽいけど愚直に4方向のテーブルを作ってみたいな方針でやったらTLEなった。あとは頼む
# ↑ やりました（4ヶ月ぶり） -> 駄目でした TLE
h, w = map(int, input().split())
grid = []
for _ in range(h):
    grid.append(list(input()))

toR, toL = (
    [[0 for _ in range(w + 1)] for _ in range(h)],
    [[0 for _ in range(w + 1)] for _ in range(h)],
)
toU, toD = (
    [[0 for _ in range(w)] for _ in range(h + 1)],
    [[0 for _ in range(w)] for _ in range(h + 1)],
)


for y in range(h):
    for x in range(w):
        if grid[y][x] == ".":
            toR[y][x + 1] += toR[y][x] + 1
            toD[y + 1][x] += toD[y][x] + 1
        else:
            toR[y][x + 1] = 0
            toD[y + 1][x] = 0

        if grid[y][w - x - 1] == ".":
            toL[y][w - x - 1] += toL[y][w - x] + 1
        else:
            toL[y][w - x - 1] = 0

        if grid[h - y - 1][x] == ".":
            toU[h - y - 1][x] += toU[h - y][x] + 1
        else:
            toU[h - y - 1][x] = 0

ans = 0
for y in range(h):
    for x in range(w):
        tmp = toR[y][x + 1] + toL[y][x] + toD[y + 1][x] + toU[y][x] - 3
        ans = max(ans, tmp)

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
H,W=map(int, input().split())
S=np.array([list(input()) for i in range(H)]) == '.'
us=np.zeros((H,W), dtype=int)   
ds=np.zeros((H,W), dtype=int)   
ls=np.zeros((H,W), dtype=int)    
rs=np.zeros((H,W), dtype=int)  

for h in range(1,H):
    us[h, :]=(us[h-1, :]+1) * S[h-1, :]
for h in range(H-2, -1, -1):
    ds[h, :]=(ds[h+1, :]+1) * S[h+1, :]
for w in range(1,W):
    ls[:, w]=(ls[:, w-1]+1) * S[:, w-1]
for w in range(W-2, -1, -1):
    rs[:, w]=(rs[:, w+1]+1) * S[:, w+1]

ans = ((us+ds+ls+rs)*S).max()+1
print(ans)

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

h,w = LI()
s = [list(input()) for _ in range(h)]
W = [[0]*w for _ in range(h)]
H = [[0]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if s[i][j] == '#':
            continue
        else:
            if j > 0:
                W[i][j] = W[i][j-1] + 1
            else:
                W[i][j] = 1
            if i > 0:
                H[i][j]  = H[i-1][j] + 1
            else:
                H[i][j] = 1
y = [[0]*w for _ in range(h)]
x = [[0]*w for _ in range(h)]
for i in range(h)[::-1]:
    for j in range(w)[::-1]:
        if j == w-1:
            x[i][j] = W[i][j]
        if j > 0:
            if s[i][j-1] != '#':
                if s[i][j] == '#':
                    x[i][j-1] = W[i][j-1]
                else:
                    x[i][j-1] = max(x[i][j],W[i][j])
        if i == h-1:
            y[i][j] = H[i][j]
        if i > 0:
            if s[i-1][j] != '#':
                if s[i][j] == '#':
                    y[i-1][j] = H[i-1][j]
                else:
                    y[i-1][j] = max(y[i][j],H[i][j])
ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] != '#':
            ans = max(ans,x[i][j] + y[i][j]-1)
print(ans)

Submission status: Accepted

Solution code:
import sys

if sys.platform in ['ios','win32','darwin']:
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

def main():
	H, W = MAP()
	M = [input().rstrip() for _ in range(H)]

	DU = tuple([-1,1])
	LR = tuple([-1,1])
	memo = [[-1]*W for _ in range(H)]
	ans = 0
	for i in range(H):
		for j in range(W):
			if M[i][j] == '#': continue
			tmp = [0,0]
			
			skip = -1
			if memo[i-1][j] != -1:
				tmp[0] = memo[i-1][j][0]
				skip = 1
			if memo[i][j-1] != -1:
				tmp[1] = memo[i][j-1][1]
				skip = 5 if skip == 1 else 2
			
			if skip == 1 or skip == -1:
				lr = 0
				for move in LR:
					nw = j
					dw = move
					while True:
						nw += dw
						# print(i, j, nh, nw)
						if nw>W-1 or nw<0 or M[i][nw] == '#': break
						lr += 1
					tmp[1] = lr

			if skip == 2 or skip == -1:
				du = 0
				for move in DU:
					nh = i
					dh = move
					while True:
						nh += dh
						# print(i, j, nh, nw)
						if nh>H-1 or nh<0 or M[nh][j] == '#': break
						du += 1
					tmp[0] = du
			
			memo[i][j] = tuple(tmp)
			ans = max(ans, sum(tmp)+1)
		
	# for mem in memo:
	# 	print(mem)
	# for m in M:
	# 	print(m)
	print(ans)

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
H,W = map(int,input().split())
S = ['#' * (W+2)]
for _ in range(H):
    S.append('#' + input() + '#')
S.append('#' * (W+2))

h = [[0] * (W+1) for _ in range(H+1)]
v = [[0] * (W+1) for _ in range(H+1)]

for y in range(1, H+2):
    l = 0
    r = 0
    for x in range(1, W+2):
        if S[y][x] == '.':
            if S[y][x-1] == '#':
                l = x
            r = x
        else:
            if S[y][x-1] == '.':
                for x1 in range(l,r+1):
                    h[y][x1] = r - l + 1

for x in range(1, W+2):
    t = 0
    b = 0
    for y in range(1, H+2):
        if S[y][x] == '.':
            if S[y-1][x] == '#':
                t = y
            b = y
        else:
            if S[y-1][x] == '.':
                for y1 in range(t,b+1):
                    v[y1][x] = b - t + 1

ans = 0
for x in range(1, W+1):
    for y in range(1, H+1):
        ans = max(ans, h[y][x]+v[y][x]-1)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

H, W = map(int, input().split())
F = []
for _ in range(H):
    a = list(input())[:-1]
    F.append(a)

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+1):
    f = F[h-1]
    l = L[h]
    for w in range(1, W+1):
        l[w] = l[w-1] + 1 if f[w-1] == '.' else 0
        U[h][w] = U[h-1][w] + 1 if f[w-1] == '.' else 0

for h in range(H, 0, -1):
    f = F[h-1]
    r = R[h]
    for w in range(W, 0, -1):
        r[w] = r[w+1] + 1 if f[w-1] == '.' else 0
        D[h][w] = D[h+1][w] + 1 if f[w-1] == '.' else 0

ans = 0
for h in range(1, H+1):
    l, r, u, d = L[h], R[h], U[h], D[h]
    ans = max( ans, max( l[w]+r[w]+u[w]+d[w] for w in range(1, W+1) ))
print(ans-3)

Submission status: Accepted

Solution code:
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)]    
    T = [[0] * W for _ in range(H)]
    D = [[0] * W for _ in range(H)]

    for h in range(H):
        cnt = 1
        for w in range(W):
            if S[h][w] == '#':
                cnt = 1
            else:
                L[h][w] = cnt
                cnt += 1

    for h in range(H):
        cnt = 1
        for w in range(W-1,-1,-1):
            if S[h][w] == '#':
                cnt = 1
            else:
                R[h][w] = cnt
                cnt += 1

    for w in range(W):
        cnt = 1
        for h in range(H):
            if S[h][w] == '#':
                cnt = 1
            else:
                T[h][w] = cnt
                cnt += 1

    for w in range(W):
        cnt = 1
        for h in range(H-1,-1,-1):
            if S[h][w] == '#':
                cnt = 1
            else:
                D[h][w] = cnt
                cnt += 1

    ans = 0
    for h in range(H):
        for w in range(W):
            tmp = T[h][w] + D[h][w] + L[h][w] + R[h][w] - 3
            ans = max(ans, tmp)

    print(ans)

if __name__ == "__main__":
    main()