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 = list(map(int, input().split()))
d = [[0 for _ in range(W)] for _ in range(H)]

for i in range(H):
    for j, x in enumerate(list(input())):        
        if x == "#":
            s = 0
        else:
            s = 1
        d[i][j] = s

# 自分より左のOKマスの数
L = [[0 for _ in range(W)] for _ in range(H)]
# 自分より右のOKマスの数
R = [[0 for _ in range(W)] for _ in range(H)]
# 自分より上のOKマスの数
U = [[0 for _ in range(W)] for _ in range(H)]
# 自分より下のOKマスの数
D = [[0 for _ in range(W)] for _ in range(H)]

for i in range(H):
    for j in range(W):
        # for L
        if d[i][j]:
            if j == 0:
                L[i][j] = 1            
            else:
                L[i][j] = L[i][j-1] + 1
        else:
            L[i][j] = 0
        
        # for R
        rj = W - j - 1
        if d[i][rj]:
            if rj == W-1:
                R[i][rj] = 1            
            else:
                R[i][rj] = R[i][rj+1] + 1
        else:
            R[i][rj] = 0
        
        # for U        
        if d[i][j]:
            if i == 0:
                U[i][j] = 1            
            else:
                U[i][j] = U[i-1][j] + 1
        else:
            U[i][j] = 0
     
        # for D
        di = H - i - 1
        if d[di][j]:
            if di == H-1:
                D[di][j] = 1            
            else:
                D[di][j] = D[di+1][j] + 1
        else:
            D[di][j] = 0

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

Submission status: Accepted

Solution code:
# D - Lamp
import numpy as np

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

# 0: 障害物または壁 1: 通路
# 上下左右の壁の分を加味して+2したグリッドを用意する。
g = np.zeros((h+2,w+2),dtype=np.int64)
for i in range(h):
    grid = np.array(list(input()))
    g[i+1, 1:w+1] = (grid=='.')

# 横について考える
gW = np.copy(g)
gW = np.ravel(gW)
tWLeft = np.arange((w+2)*(h+2))
tWRight = np.copy(tWLeft)

tWLeft[gW==1] = 0
tWRight[gW[::-1]==1] = 0

np.maximum.accumulate(tWLeft, out=tWLeft)
np.maximum.accumulate(tWRight, out=tWRight)

tWRight = len(tWRight) - 1 - tWRight[::-1]

tW = tWRight-tWLeft-1
tW[gW==0] = 0
tW = tW.reshape(h+2, w+2)

# 縦について考える
gH = np.copy(g.T)
gH = np.ravel(gH)
tHLeft = np.arange((w+2)*(h+2))
tHRight = np.copy(tHLeft)

tHLeft[gH==1] = 0
tHRight[gH[::-1]==1] = 0

np.maximum.accumulate(tHLeft, out=tHLeft)
np.maximum.accumulate(tHRight, out=tHRight)

tHRight = len(tHRight) - 1 - tHRight[::-1]

tH = tHRight-tHLeft-1
tH[gH==0] = 0
tH = tH.reshape(w+2, h+2).T

#print(tW)
#print(tH)
print(np.max(tW+tH-1))


'''
# 横について考える
tblW = np.zeros((h, w),dtype=np.int64)
for i in range(h):
    for j in range(w):
        if grid[i, j]=='#' or tblW[i, j]>0:
            continue
        else:
            cnt = 1
            while j+cnt<w and grid[i, j+cnt]!='#':
                cnt += 1
            tblW[i, j:j+cnt] = cnt
print(tblW)
    
# 縦について考える
tblH = np.zeros((h, w),dtype=np.int64)
for j in range(w):
    for i in range(h):
        if grid[i, j]=='#' or tblH[i, j]>0:
            continue
        else:
            cnt = 1
            while i+cnt<h and grid[i+cnt, j]!='#':
                cnt += 1
            tblH[i:i+cnt, j] = cnt
print(tblH)

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

print(ans)
'''

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni      = lambda: int(ns())
nin     = lambda y: [ni() for _ in range(y)]
na      = lambda: list(map(int, stdin.readline().split()))
nan     = lambda y: [na() for _ in range(y)]
nf      = lambda: float(ns())
nfn     = lambda y: [nf() for _ in range(y)]
nfa     = lambda: list(map(float, stdin.readline().split()))
nfan    = lambda y: [nfa() for _ in range(y)]
ns      = lambda: stdin.readline().rstrip()
nsn     = lambda y: [ns() for _ in range(y)]
ncl     = lambda y: [list(ns()) for _ in range(y)]
nas     = lambda: stdin.readline().split()

h, w = na()
s = nsn(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
        else:
            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 - 1, -1, -1):
    for j in range(w - 1, -1, -1):
        if s[i][j] == '#':
            r[i][j] = 0
            d[i][j] = 0
        else:
            if j == w - 1:
                r[i][j] = 1
            else:
                r[i][j] = r[i][j + 1] + 1
            
            if i == h - 1:
                d[i][j] = 1
            else:
                d[i][j] = d[i + 1][j] + 1

ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans, l[i][j] + r[i][j] + u[i][j] + d[i][j] - 3)

print(ans)

Submission status: Accepted

Solution code:
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


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


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

    hori = [[0 for _ in range(W)] for _ in range(H)]
    for i in range(H):
        cnt = 0
        for j in range(W):
            if S[i][j] == '.':
                cnt += 1
                hori[i][j] = cnt
            else:
                cnt = 0
        res = 0
        for j in range(W - 1, -1, -1):
            if S[i][j] == '.':
                res = max(res, hori[i][j])
                hori[i][j] = res
            else:
                res = 0

    vert = [[0 for _ in range(W)] for _ in range(H)]
    for i in range(W):
        cnt = 0
        for j in range(H):
            if S[j][i] == '.':
                cnt += 1
                vert[j][i] = cnt
            else:
                cnt = 0
        res = 0
        for j in range(H - 1, -1, -1):
            if S[j][i] == '.':
                res = max(res, vert[j][i])
                vert[j][i] = res
            else:
                res = 0

    ans = 0
    for i in range(H):
        for j in range(W):
            if S[i][j] == '.':
                ans = max(ans, hori[i][j] + vert[i][j] - 1)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W = lr()
S = [list(sr()) for _ in range(H)]
S = np.array([[1 if x == '.' else 0 for x in row] for row in S], np.bool)
up = np.zeros((H, W), np.int32)
down = np.zeros((H, W), np.int32)
right = np.zeros((H, W), np.int32)
left = np.zeros((H, W), np.int32)
for i in range(H-1):
    up[i+1] = (1+up[i]) * S[i]
for i in range(H-1, 0, -1):
    down[i-1] = (1+down[i]) * S[i]
for i in range(W-1):
    left[:, i+1] = (1+left[:, i]) * S[:, i]
    #行列の列を取り出す時の記法
for i in range(W-1, 0, -1):
    right[:, i-1] = (1+right[:, i]) * S[:, i]


answer = ((up + down + left + right) * S).max() + 1
#自身を数えないことで特殊な場合をなくしている
print(answer)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
grid = []
grid_num1 = []
grid_num2 = []
for i in range(h):
    lst = list(input())
    lst.append("#")
    grid.append(lst)
    grid_num1.append([0]*w)
grid.append(["#"]*(w+1))
for j in range(w):
    grid_num2.append([0]*h)

grid_t = [list(x) for x in zip(*grid)]

for i in range(h):
    sw = []
    tar_row = grid[i]
    for j in range(w+1):
        if j == 0 and tar_row[j] == ".":
            sw.append(j)
        elif tar_row[j] == "." and tar_row[j-1] == "#":
            sw.append(j)
        elif tar_row[j] == "#" and tar_row[j-1] == ".":
            sw.append(j)
    for j in range(0,len(sw),2):
        l = sw[j]
        r = sw[j+1]
        for k in range(l, r):
            grid_num1[i][k] += r-l

for i in range(w):
    sw = []
    tar_row = grid_t[i]
    for j in range(h+1):
        if j == 0 and tar_row[j] == ".":
            sw.append(j)
        elif tar_row[j] == "." and tar_row[j-1] == "#":
            sw.append(j)
        elif tar_row[j] == "#" and tar_row[j-1] == ".":
            sw.append(j)
    for j in range(0,len(sw),2):
        l = sw[j]
        r = sw[j+1]
        for k in range(l, r):
            grid_num2[i][k] += r-l
# grid_num2 = [list(x) for x in zip(*grid_num2)]

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

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
grid = []
grid_num1 = []
grid_num2 = []
for i in range(h):
    lst = list(input())
    lst.append("#")
    grid.append(lst)
    grid_num1.append([0]*w)
grid.append(["#"]*(w+1))
for j in range(w):
    grid_num2.append([0]*h)

grid_t = [list(x) for x in zip(*grid)]

for i in range(h):
    sw = []
    tar_row = grid[i]
    for j in range(w+1):
        if j == 0 and tar_row[j] == ".":
            sw.append(j)
        elif tar_row[j] == "." and tar_row[j-1] == "#":
            sw.append(j)
        elif tar_row[j] == "#" and tar_row[j-1] == ".":
            sw.append(j)
    for j in range(0,len(sw),2):
        l = sw[j]
        r = sw[j+1]
        for k in range(l, r):
            grid_num1[i][k] += r-l

for i in range(w):
    sw = []
    tar_row = grid_t[i]
    for j in range(h+1):
        if j == 0 and tar_row[j] == ".":
            sw.append(j)
        elif tar_row[j] == "." and tar_row[j-1] == "#":
            sw.append(j)
        elif tar_row[j] == "#" and tar_row[j-1] == ".":
            sw.append(j)
    for j in range(0,len(sw),2):
        l = sw[j]
        r = sw[j+1]
        for k in range(l, r):
            grid_num2[i][k] += r-l
grid_num2 = [list(x) for x in zip(*grid_num2)]

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

Submission status: Accepted

Solution code:
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
        else:
            if j == 0:
                l[i][j] = 1
            else:
                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
            else:
                r[i][j] = r[i][j+1] + 1

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

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

ans = 0

for i in range(h):
    for j in range(w):
        ans = max(ans, l[i][j] + r[i][j] + u[i][j] + d[i][j] - 3)

print(ans)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
c = [[] for i in range(h)]
d = [[1]*w for _ in range(h)]
e = [[1]*w for _ in range(h)]
for i in range(h):
    c[i] = input()
    if c[i][0] == "#":
        d[i][0] = 0
for i in range(w):
    if c[0][i] == "#":
        e[0][i] = 0
    
for i in range(h):
    for j in range(w-1):
        if c[i][j+1] == "#":
            d[i][j+1] = 0
        else:
            d[i][j+1] = d[i][j] + 1
            
for i in range(h-1):
    for j in range(w):
        if c[i+1][j] == "#":
            e[i+1][j] = 0
        else:
            e[i+1][j] = e[i][j] + 1
            
for i in range(h):
    for j in range(w-2,-1,-1):
        if d[i][j] != 0 and d[i][j+1] != 0:
            d[i][j] = d[i][j+1]
        elif d[i][j] != 0 and d[i][j+1] == 0:
            continue
        else:
            d[i][j] = 0
            
for i in range(h-2,-1,-1):
    for j in range(w):
        if e[i][j] != 0 and e[i+1][j] != 0:
            e[i][j] = e[i+1][j]
        elif e[i][j] != 0 and e[i+1][j] == 0:
            continue
        else:
            e[i][j] = 0
            
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans , d[i][j]+e[i][j])
        
print(ans-1)

Submission status: Accepted

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

result = [[0]*W for _ in range(H)]
for i in range(H):
    c = 0
    start = 0
    for j in range(W):
        if T[i][j] == "#":
            for k in range(start,j):
                result[i][k] += c
            start = j + 1
            c = 0
        elif j == W-1:
            c += 1
            for k in range(start,j+1):
                result[i][k] += c
        else:
            c += 1

for i in range(W):
    c = 0
    start = 0
    for j in range(H):
        if T[j][i] == "#":
            for k in range(start,j):
                result[k][i] += c
            start = j + 1
            c = 0
        elif j == H-1:
            c += 1
            for k in range(start,j+1):
                result[k][i] += c
        else:
            c += 1

ans = 0
for i in range(H):
    for j in range(W):
        if T[i][j] == ".":
            ans = max(ans,result[i][j]-1)
        else:
            ans = max(ans,result[i][j])
print(ans)

Submission status: Accepted

Solution code:
def main():
    H, W = map(int, input().split())
    S = []
    for _ in range(H):
        s = list(input())
        S.append(s)
    R = [[0]*W for _ in range(H)]
    L = [[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):
        cnt = 0
        for j in range(W):
            if S[i][j]=='#':
                cnt = 0
            else:
                cnt += 1
                L[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
                R[i][j] = cnt
    for j in range(W):
        cnt = 0
        for i in range(H):
            if S[i][j]=='#':
                cnt = 0
            else:
                cnt += 1
                U[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
                D[i][j] = cnt
    ans = 0
    for i in range(H):
        for j in range(W):
            ans = max(ans, L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    numLss = [[0]*(W+2) for _ in range(H+2)]
    numRss = [[0]*(W+2) for _ in range(H+2)]
    numUss = [[0]*(W+2) for _ in range(H+2)]
    numDss = [[0]*(W+2) for _ in range(H+2)]
    for i in range(1, H+1):
        for j in range(1, W+1):
            if Sss[i][j] == '.':
                numLss[i][j] = numLss[i][j-1] + 1
        for j in reversed(range(1, W+1)):
            if Sss[i][j] == '.':
                numRss[i][j] = numRss[i][j+1] + 1
    for j in range(1, W+1):
        for i in range(1, H+1):
            if Sss[i][j] == '.':
                numUss[i][j] = numUss[i-1][j] + 1
        for i in reversed(range(1, H+1)):
            if Sss[i][j] == '.':
                numDss[i][j] = numDss[i+1][j] + 1

    ans = 0
    for i in range(1, H+1):
        for j in range(1, W+1):
            num = numLss[i][j] + numRss[i][j] + numUss[i][j] + numDss[i][j] - 3
            ans = max(ans, num)

    print(ans)


solve()

Submission status: Accepted

Solution code:
import numpy as np

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

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

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

for h in range(H):
    if h == 0:
        U[h,:] = S_list[h,:]
        D[H-h-1,:] = S_list[H-h-1,:]
    else:
        U[h,:] = (U[h-1,:]+1) * S_list[h,:]
        D[H-h-1,:] = (D[H-h,:]+1) * S_list[H-h-1,:]
        
ans = max(np.max(L+R+U+D-3), 0)

print(ans)

Submission status: Accepted

Solution code:
h,w = map(int,input().split())
maps = [ input() for _ in range(h)]
ans = 0

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

for y in range(h):
    for x in range(w):
        if maps[y][x] == "#":
            U[y][x],L[y][x] = 0,0
        else:
            if y == 0 and x >= 1:
                U[0][x] = 1
                L[y][x] += 1 + L[y][x-1]
            elif x == 0 and y >= 1: 
                U[y][x] += 1 + U[y-1][x]
                L[y][0] = 1
            elif x == 0 and y == 0:
                U[y][x] = 1
                L[y][x] = 1
            else:
                U[y][x] += 1 + U[y-1][x]
                L[y][x] += 1 + L[y][x-1]

for y in range(h-1,-1,-1):
    for x in range(w-1,-1,-1):
        if maps[y][x] == "#":
            D[y][x],R[y][x] = 0,0
        else:
            if y == h-1 and x < w-1:
                D[y][x] = 1
                R[y][x] += 1 + R[y][x+1]
            elif x == w-1 and y < h-1:
                D[y][x] += 1 + D[y+1][x]
                R[y][x] = 1
            elif  x == w-1 and y == h-1:
                D[y][x] = 1
                R[y][x] = 1
            else:
                D[y][x] += 1 + D[y+1][x]
                R[y][x] += 1 + R[y][x+1]

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

Submission status: Accepted

Solution code:
import numpy as np
h,w = map(int,input().split())
ar = np.array([list(input()) for _ in range(h)]) == '.'
#print(ar)
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):
  u[i] = (u[i-1]+1)*ar[i]
  #print(u)
  d[-i-1] = (d[-i]+1)*ar[-i-1]
  #print(d)
  
for j in range(w):
  l[:,j] = (l[:,j-1]+1)*ar[:,j]
  #print(l)
  r[:,-j-1] = (r[:,-j]+1)*ar[:,-j-1]
  #print(r)
print(np.max(u+d+l+r)-3)

Submission status: Accepted

Solution code:
import numpy as np

h, w = map(int, input().split())
S = list(list(input()) for _ in range(h))
S = np.array(S)
S_int = np.zeros_like(S, dtype=int)
S_int[S=='.'] = 1

def getLR(d, width, height):
  L = np.zeros_like(d)
  R = L.copy()
  L[:][0] = 0
  R[:][-1] = 0
  for i in range(1, width):
    ridx = width - 1 - i
    L[:,i] = d[:,i] * (L[:,i-1] + d[:,i-1])
    R[:,ridx] = d[:,ridx] * (R[:,ridx+1] + d[:,ridx+1])
  return L, R

L, R = getLR(S_int, w, h)
U, D = getLR(S_int.T, h, w)
print((L+R+U.T+D.T).max() + 1)

Submission status: Accepted

Solution code:
import numpy as np

H,W = map(int,input().split())
temp = np.array([list(input()) for _ in range(H)])
# 周りに壁を、0,1化
map = np.zeros((H+2,W+2),dtype=np.int32)
map[1:-1,1:-1][temp == '.'] = 1

# x軸正方向の集計
def F():
  x = map.copy()
  for row in range(1,H+1):
    zero_idx = np.nonzero(x[row]==0)[0]
    x[row, zero_idx[1:]] = 1-np.diff(zero_idx) # cumsumで求められるように変形
  x = x.cumsum(axis = 1)
  return x

# y軸
def G():
  x = map.T.copy()
  for row in range(1,W+1):
    zero_idx = np.nonzero(x[row]==0)[0]
    x[row, zero_idx[1:]] = 1-np.diff(zero_idx) # cumsumで求められるように変形
  x = x.cumsum(axis = 1)
  return x.T

answer = np.zeros_like(map)
# x軸
answer += F()
# 逆順
map = map[:,::-1]
answer += F()[:,::-1]
map = map[:,::-1]

# y軸
answer += G()
# 逆順
map = map[::-1,:]
answer += G()[::-1,:]

answer = np.max(answer) - 3
print(answer)

Submission status: Accepted

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

# そのマスを含めてLeft, Right, Up, Downにそれぞれ何マス分明かりを照らせるかを配列に記録
L = [[0] * W for _ in range(H)]
R = [[0] * W for _ in range(H)]
D = [[0] * W for _ in range(H)]
U = [[0] * W for _ in range(H)]

for i in range(H):
	for j in range(W):
		if S[i][j] == ".":
			if j == 0:
				L[i][j] = 1
			else:
				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] == ".":
			if j == W - 1:
				R[i][j] = 1
			else:
				R[i][j] = R[i][j + 1] + 1

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

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


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

print(ans)

Submission status: Accepted

Solution code:
"""
参考
blog名  ベスパリブ    #プログラミングを主とした日記・備忘録です
URL     https://takeg.hatenadiary.jp/entry/2019/09/10/234417
id:     takeg
"""
# 初期入力
H,W = (int(x) for x in input().split())
S = [list(input()) for i in range(H)]
import numpy as np
S_np = (np.array(S) ==".")*1 #文字を数字に変換 Trueの所のみ演算、Falseは０


#置いたマス(i,j)から4方向探す
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 S_int[i,j] ==0:これはいらない？⇒*S_npで１or０をかけてるから不要
    if i == 0: 
        L[:,i]      = S_np[:,i]
        R[:,W-i-1]  = S_np[:,W-i-1]
    else:
        L[:,i]      = (L[:,i-1] +1) * S_np[:,i]
        R[:,W-i-1]  = (R[:,W-i] +1) * S_np[:,W-i-1]

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

#各方向を位置ごとに足す(numpyなら足すだけで行列の和) 
light = L + R + D + U -3 #基準点を4方向＋１してるからー３
light_max = np.max(light)
print(light_max)

Submission status: Accepted

Solution code:
# 初期入力
H,W = (int(x) for x in input().split())
S = [list(input()) for i in range(H)]
import numpy as np
S_np = (np.array(S) ==".")*1 #文字を数字に変換 Trueの所のみ演算、Falseは０


#置いたマス(i,j)から4方向探す
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 S_int[i,j] ==0:これはいらない？⇒*S_npで１or０をかけてるから不要
    if i == 0: 
        L[:,i]      = S_np[:,i]
        R[:,W-i-1]  = S_np[:,W-i-1]
    else:
        L[:,i]      = (L[:,i-1] +1) * S_np[:,i]
        R[:,W-i-1]  = (R[:,W-i] +1) * S_np[:,W-i-1]

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

#各方向を位置ごとに足す(numpyなら足すだけで行列の和) 
light = L + R + D + U -3 #基準点を4方向＋１してるからー３
light_max = np.max(light)
print(light_max)

Submission status: Accepted

Solution code:
def main():
    h, w = [int(e) for e in input().split()]
    S = [input() for i in range(h)]

    L = [[0] * (w + 2) for i in range(h + 2)]
    R = [[0] * (w + 2) for i in range(h + 2)]
    T = [[0] * (w + 2) for i in range(h + 2)]
    B = [[0] * (w + 2) for i in range(h + 2)]
    for hi in range(1, h + 1):
        for wi in range(1, w + 1):
            if S[hi - 1][wi - 1] == '.':
                L[hi][wi] = L[hi][wi - 1] + 1
                T[hi][wi] = T[hi - 1][wi] + 1

            if S[hi - 1][-wi] == '.':
                R[hi][-wi - 1] = R[hi][-wi] + 1

            if S[-hi][wi - 1] == '.':
                B[-hi - 1][wi] = B[-hi][wi] + 1

    ans = 0
    for hi in range(1, h + 1):
        for wi in range(1, w + 1):
            ans = max(L[hi][wi] + R[hi][wi] + T[hi][wi] + B[hi][wi] - 3, ans)

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
S=[[i for i in list(input())]for _ in range(H)]
L=[[0]*W for _ in range(H)]
R=[[0]*W for _ in range(H)]
U=[[0]*W for _ in range(H)]
D=[[0]*W for _ in range(H)]
for i in range(H):
    count=0
    for j in range(W):
        if S[i][j]=="#":
            count=0
        else:
            count=count+1
        L[i][j]=count
for i in range(H):
    count=0
    for j in range(W)[::-1]:
        if S[i][j]=="#":
            count=0
        else:
            count=count+1
        R[i][j]=count
for i in range(W):
    count=0
    for j in range(H):
        if S[j][i]=="#":
            count=0
        else:
            count=count+1
        U[j][i]=count
for i in range(W):
    count=0
    for j in range(H)[::-1]:
        if S[j][i]=="#":
            count=0
        else:
            count=count+1
        D[j][i]=count
ans=0
for i in range(H):
    for j in range(W):
        ans=max(ans,L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
h,w = map(int,input().split())
s = [[] for j in range(h)]
for i in range(h):
    tmp = input()
    for j in tmp:
        if j == '.':
            s[i].append(1)
        else:
            s[i].append(0)


L = np.zeros((h,w))
R = np.zeros((h,w))
U = np.zeros((h,w))
D = np.zeros((h,w))
s = np.array(s)

for i in range(w):
    L[:,i] = (L[:,i-1]+1)*s[:,i]
    R[:,-1-i] = (R[:,-i]+1)*s[:,-1-i]
    
for i in range(h):
    U[i,:] = (U[i-1,:]+1)*s[i,:]
    D[-1-i,:] = (D[-i,:]+1)*s[-i-1,:]
    
print(int(np.max(L+R+D+U-3)))

Submission status: Accepted

Solution code:
import sys
import numpy as np
def main():
    input = sys.stdin.readline
    h, w = map(int, input().split())
    s = np.array([list(input().rstrip()) for _ in range(h)])
    t = np.zeros((h+2, w+2))
    t[1:-1, 1:-1][s == "."] = 1
    row = np.zeros((h+2, w+2))
    col = np.zeros((w+2, h+2))
    for i in range(1, h+1):
        idx = np.where(t[i] == 0)[0]
        dif = np.diff(idx)
        row[i, idx[:-1]+1] += dif-1
        row[i, idx[1:]] -= dif-1
        row[i] = np.cumsum(row[i])
    t = t.T
    for i in range(1, w+1):
        idx = np.where(t[i] == 0)[0]
        dif = np.diff(idx)
        col[i, idx[:-1]] += dif-2
        col[i, idx[1:]] -= dif-2
        col[i] = np.cumsum(col[i])
    col = col.T
    cost = np.add(row, col)
    print(int(np.max(cost)))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
def main():
    h, w = map(int, input().split())
    s = np.array([list(input()) for _ in range(h)])
    t = np.zeros((h+2, w+2))
    t[1:-1, 1:-1][s == "."] = 1
    row = np.zeros((h+2, w+2))
    col = np.zeros((w+2, h+2))
    for i in range(1, h+1):
        idx = np.where(t[i] == 0)[0]
        dif = np.diff(idx)
        row[i, idx[:-1]+1] += dif-1
        row[i, idx[1:]] -= dif-1
        row[i] = np.cumsum(row[i])
    t = t.T
    for i in range(1, w+1):
        idx = np.where(t[i] == 0)[0]
        dif = np.diff(idx)
        col[i, idx[:-1]] += dif-2
        col[i, idx[1:]] -= dif-2
        col[i] = np.cumsum(col[i])
    col = col.T
    cost = np.add(row, col)
    print(int(np.max(cost)))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W = lr()

S = [list(sr()) for _ in range(H)]
S = np.array([[1 if x == '.' else 0 for x in row] for row in S])

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

for h in range(H-1):
    U[h+1] = (U[h] + 1) * S[h]
    D[H-h-2] = (D[H-h-1] + 1) * S[H-h-1]
for w in range(W-1):
    L[:, w+1] = (L[:, w] + 1) * S[:, w]
    R[:, W-w-2] = (R[:, W-w-1] + 1) * S[:, W-w-1]


print(((U + D + L + R) * S).max() + 1)

Submission status: Accepted

Solution code:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

H, W = lr()

S = [list(sr()) for _ in range(H)]
S = np.array([[1 if x == '.' else 0 for x in row] for row in S])

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

for h in range(H-1):
    U[h+1] = (U[h] + 1) * S[h]
    D[H-h-2] = (D[H-h-1] + 1) * S[H-h-1]
for w in range(W-1):
    L[:, w+1] = (L[:, w] + 1) * S[:, w]
    R[:, W-w-2] = (R[:, W-w-1] + 1) * S[:, W-w-1]


print(((U + D + L + R) * S).max() + 1)

Submission status: Accepted

Solution code:
H,W=map(int,input().split())
S=[list(input()) for _ in range(H)]
#print(S)
Syoko=[[0 for _ in range(W)] for _ in range(H)]
State=[[0 for _ in range(W)] for _ in range(H)]
#まず横から連続する壁のない領域をcountし、Syokoにいれる
for i in range(H):
    cnt=0
    id=0
    buf=[]
    for j in range(W):
        if S[i][j]=="#":
            buf.append(j)
    buf.append(W+1)
    for j in range(W):
        if buf[id]!=j:
            if id==0:
                Syoko[i][j]=min(buf[0],W)
            elif id==len(buf)-1:
                Syoko[i][j]=(W-1)-buf[id-1]
            else:
                Syoko[i][j]=buf[id]-(buf[id-1]+1)
        else:
            id=id+1
#print(Syoko)
for j in range(W):
    cnt=0
    id=0
    buf=[]
    for i in range(H):
        if S[i][j]=="#":
            buf.append(i)
    buf.append(H+1)
    for i in range(H):
        if buf[id]!=i:
            if id==0:
                State[i][j]=min(buf[0],H)
            elif id==len(buf)-1:
                State[i][j]=(H-1)-buf[id-1]
            else:
                State[i][j]=buf[id]-(buf[id-1]+1)
        else:
            id=id+1
#print(State)
ma=0
for i in range(H):
    for j in range(W):
        ma=max(ma,State[i][j]+Syoko[i][j]-1)
print(ma)