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:
from sys import stdin
import numpy as np
def main():
    #入力
    readline=stdin.readline
    h,w=map(int,readline().split())
    grid=[readline().strip() for _ in range(h)]
    grid2=np.zeros((h,w),dtype="int64")
    for i in range(h):
        for j in range(w):
            if grid[i][j]==".":
                grid2[i][j]=1
            else:
                grid2[i][j]=0

    up=np.zeros((h,w),dtype="int64")
    up[0]=grid2[0]
    for i in range(1,h):
        up[i]=(up[i-1]+1)*grid2[i]
    
    down=np.zeros((h,w),dtype="int64")
    down[-1]=grid2[-1]
    for i in range(h-2,-1,-1):
        down[i]=(down[i+1]+1)*grid2[i]
    
    left=np.zeros((h,w),dtype="int64")
    left[:,0]=grid2[:,0]
    for i in range(1,w):
        left[:,i]=(left[:,i-1]+1)*grid2[:,i]
    
    right=np.zeros((h,w),dtype="int64")
    right[:,-1]=grid2[:,-1]
    for i in range(w-2,-1,-1):
        right[:,i]=(right[:,i+1]+1)*grid2[:,i]

    ans=(up+down+left+right-3).max()
    print(ans)
    
if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
import sys
 
def main():
    sin = sys.stdin.buffer
    H, W = map(int, sin.readline().split())
    grid = np.frombuffer(sin.read(H * (W + 1)), dtype="B") == ord(".")
    grid = grid.reshape((H, W + 1))[:, :-1]
 
    L = np.empty((H, W), dtype="i4")
    R = np.empty((H, W), dtype="i4")
    T = np.empty((H, W), dtype="i4")
    B = np.empty((H, W), dtype="i4")
 
    T[0] = grid[0]
    for i in range(1, H):
        T[i] = (T[i - 1] + 1) * grid[i]
 
    B[-1] = grid[-1]
    for i in range(H - 2, -1, -1):
        B[i] = (B[i + 1] + 1) * grid[i]
 
    L[:, 0] = grid[:, 0]
    for i in range(1, W):
        L[:, i] = (L[:, i - 1] + 1) * grid[:, i]
 
    R[:, -1] = grid[:, -1]
    for i in range(W - 2, -1, -1):
        R[:, i] = (R[:, i + 1] + 1) * grid[:, i]
 
    ans = (T + B + L + R - 3).max()
    print(ans)
 
main()

Submission status: Accepted

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

# 各マスから左に何マスいったら壁にぶつかるか
left = [[-1 for _ in range(W)] for _ in range(H)]
right = [[-1 for _ in range(W)] for _ in range(H)]
top = [[-1 for _ in range(W)] for _ in range(H)]
bottom = [[-1 for _ in range(W)] for _ in range(H)]


# 左に何マスいったらぶつかるか
for i in range(H):
    count = 0
    for j in range(W):
        if Ss[i][j] == "#":
            count = 0
        else:
            left[i][j] = count
            count += 1

# 右に何マスいったらぶつかるか
for i in range(H):
    count = 0
    for j in range(W):
        k = W-j-1
        if Ss[i][k] == "#":
            count = 0
        else:
            right[i][k] = count
            count += 1

# 上に何マスいったらぶつかるか
for j in range(W):
    count = 0
    for i in range(H):
        if Ss[i][j] == "#":
            count = 0
        else:
            top[i][j] = count
            count += 1

# 下に何マスいったらぶつかるか
for j in range(W):
    count = 0
    for i in range(H):
        k = H - i - 1
        if Ss[k][j] == "#":
            count = 0
        else:
            bottom[k][j] = count
            count += 1

# print("right")
# for i in range(H):
#     print(right[i])
#
# print("left")
# for i in range(H):
#     print(left[i])
#
# print("bottom")
# for i in range(H):
#     print(bottom[i])
#
# print("top")
# for i in range(H):
#     print(top[i])

max_score = 0
for i in range(H):
    for j in range(W):
        if Ss[i][j] != "#":
            score = left[i][j] + right[i][j] + top[i][j] + bottom[i][j] + 1
            max_score = max(max_score, score)

print(max_score)

Submission status: Accepted

Solution code:
h, w = map(int, input().split())
s = []
for _ in range(h):
    s.append(input())
r = [[0]*w for _ in range(h)]
for i in range(h):
    flg = False
    for j in range(w):
        if s[i][j]=='.':
            if not flg:
                tmp = 0
                begin = j
                flg = True
            tmp += 1
        if flg and s[i][j]=='#':
            for k in range(begin, j):
                r[i][k] = tmp
            flg = False
    if flg:
        for k in range(begin, w):
            r[i][k] = tmp
c = [[0]*w for _ in range(h)]
for i in range(w):
    flg = False
    for j in range(h):
        if s[j][i]=='.':
            if not flg:
                tmp = 0
                begin = j
                flg = True
            tmp += 1
        if flg and s[j][i]=='#':
            for k in range(begin, j):
                c[k][i] = tmp
            flg = False
    if flg:
        for k in range(begin, h):
            c[k][i] = tmp
ans = 0
for row1, row2 in zip(r, c):
    for e1, e2 in zip(row1, row2):
        if ans<e1+e2-1:
            ans = e1+e2-1
print(ans)

Submission status: Accepted

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

    cnt = [[0]*w for _ in range(h)]
    for i in range(h):
        prev = [0]*w
        for j in range(w):
            if s[i][j] == '#':
                continue
            if prev[j] == 1:
                continue
            ln = 0
            while j+ln < w:
                if s[i][j+ln] == '#':
                    break
                ln += 1
            for k in range(ln):
                cnt[i][j+k] += ln
                prev[j+k] = 1
    for j in range(w):
        prev = [0]*h
        for i in range(h):
            if s[i][j] == '#':
                continue
            if prev[i] == 1:
                continue
            ln = 0
            while i+ln < h:
                if s[i+ln][j] == '#':
                    break
                ln += 1
            for k in range(ln):
                cnt[i+k][j] += ln
                prev[i+k] = 1
    res = 0
    for i in range(h):
        for j in range(w):
            res = max(res, cnt[i][j]-1)
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


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

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


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np

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

R = np.array([[0 for i in range(W)] for n in range(H)])
L = np.zeros((H, W), dtype=int)
U = np.zeros((H, W), dtype=int)
D = np.zeros((H, W), dtype=int)

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

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

Submission status: Accepted

Solution code:
import numpy as np

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

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

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

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

Submission status: Accepted

Solution code:
import numpy as np

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

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

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

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

Submission status: Accepted

Solution code:
import numpy as np
H,W=map(int,input().split(' '))
maze = [list(input()) for i in range(H)]
maze = (np.array(maze) == '.')*1
L=np.zeros((H,W),dtype=int)
R=np.zeros((H,W),dtype=int)
U=np.zeros((H,W),dtype=int)
D=np.zeros((H,W),dtype=int)
for i in range(W):
    if i==0:
        L[:,i]=maze[:,i]
        R[:,W-i-1]=maze[:,W-i-1]
    else:
        L[:,i]=(L[:,i-1]+1)*maze[:,i]
        R[:,W-i-1]=(R[:,W-i]+1)*maze[:,W-i-1]
for i in range(H):
    if i==0:
        U[i,:]=maze[i,:]
        D[H-i-1,:]=maze[H-i-1,:]
    else:
        U[i,:]=(U[i-1,:]+1)*maze[i,:]
        D[H-i-1,:]=(D[H-i]+1)*maze[H-i-1,:]
print(max(np.max(U+D+L+R-3),0))

Submission status: Accepted

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

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

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

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

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

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

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

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

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

        
        
print(ans-1)

Submission status: Accepted

Solution code:
h, w = list(map(int, input().split()))
s = [list(map(str, list(input()))) for i in range(h)]  # 文字列の二次元配列入力
yoko = [[] for _ in range(h)]
tate = [[] for _ in range(w)]
for i in range(h):
    cnt = 0
    for j in range(w):
        if j == w-1:
            if s[i][j] == '.':
                cnt += 1
                yoko[i] += [cnt] * (cnt)
            else:
                yoko[i] += [cnt] * (cnt)
                yoko[i].append(0)
        else:
            if s[i][j] == '.':
                cnt += 1
            else:
                yoko[i] += [cnt] * (cnt)
                yoko[i].append(0)
                cnt = 0

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

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

Submission status: Accepted

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


    print(ans)
    


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    H, W = (int(_) for _ in input().split())
    S = [input() for _ in range(H)]
    yoko = [[0] * W for _ in range(H)]
    tate = [[0] * W for _ in range(H)]

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

if __name__ == '__main__':
    main()

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)]) == '.' #'.'に一致するならTrueしなければFalse

    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,:] #npの変数名[k,l]でk行l列を取り出す
    for i in range(H-1):                   #:なら全部をそれぞれについて見ていく
        down[H - 2 - i,:] = (down[H - 1 - i,:] + 1) * S[H - 1 - i,:]
    for i in range(W-1):
        left[:,i+1] = (left[:,i] + 1) * S[:,i]
    for i in range(W-1):
        right[:,W - 2 - i] = (right[:,W - 1 - i] + 1) * S[:,W - 1 - i]
        
    print(((up+down+left+right)*S).max()+1) #カケザンデ要素ごとの掛け算可能
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# # D - Lamp

import numpy as np

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

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

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

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)

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

    for h in range(H):
        graph[h] = list(input())

    left = [[1]*W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if graph[h][w] == "#":
                left[h][w] = 0
            else:
                if w-1 >= 0:
                    left[h][w] = left[h][w-1] + 1

    right = [[1]*W for _ in range(H)]
    for h in range(H):
        for w in reversed(range(W)):
            if graph[h][w] == "#":
                right[h][w] = 0
            else:
                if w+1<W:
                    right[h][w] = right[h][w+1] + 1

    down = [[1]*W for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if graph[h][w] == "#":
                down[h][w] = 0
            else:
                if h-1>=0:
                    down[h][w] = down[h-1][w] + 1

    up = [[1]*W for _ in range(H)]
    for h in reversed(range(H)):
        for w in range(W):
            if graph[h][w] == "#":
                up[h][w] = 0
            else:
                if h+1<H:
                    up[h][w] = up[h+1][w] + 1

    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans,up[h][w] + down[h][w] + left[h][w] + right[h][w] - 3)


    print(ans)
    # print(up,"\n",down,"\n",left,"\n",right)
    # print(down)

if __name__ == "__main__":
  main()

Submission status: Accepted

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

H,W = (int(x) for x in input().split())
S = [list(input()) for _ in range(H)]
memh = [[0] * W for _ in range(H)]
memv = [[0] * W for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            h = memh[i][j]
            if h == 0:
                stopped = False
                for k in range(W-j-1):
                    if S[i][j+k+1] == '#':
                        for l in range(k+1):
                            memh[i][j+l] = k+1
                        stopped = True
                        break
                if stopped == False:
                    for l in range(W-j):
                        memh[i][j+l] = W-j
                h = memh[i][j]
            v = memv[i][j]
            if v == 0:
                stopped = False
                for k in range(H-i-1):
                    if S[i+k+1][j] == '#':
                        for l in range(k+1):
                            memv[i+l][j] = k+1
                        stopped = True
                        break
                if stopped == False:
                    for l in range(H-i):
                        memv[i+l][j] = H-i
                v = memv[i][j]
            ans = max(ans,h+v-1)
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
h,w=map(int,input().split())
s=[]
for _ in range(h):
    si=input()
    si=si.replace('.', '1')
    si=si.replace('#', '0')
    s.append(list(map(int,si)))
s=np.array(s)

left=np.zeros((h,w))
right=np.zeros((h,w))
up=np.zeros((h,w))
down=np.zeros((h,w))

for i in range(w):
    if(i==0):
        left[:,i]=s[:,i]
        right[:,w-i-1]=s[:,w-i-1]
    else:
        left[:,i]=(left[:,i-1]+1)*s[:,i]
        right[:,w-i-1]=(right[:,w-i]+1)*s[:,w-i-1]

for i in range(h):
    if(i==0):
        down[i,:]=s[i,:]
        up[h-i-1,:]=s[h-i-1,:]
    else:
        down[i,:]=(down[i-1,:]+1)*s[i,:]
        up[h-i-1,:]=(up[h-i,:]+1)*s[h-i-1,:]

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

Submission status: Accepted

Solution code:
import numpy as np


def main():
    H, W = list(map(int, input().split(' ')))
    field = np.array([list(input()) for _ in range(H)])
    field = np.where(field == '#', 0, 1)
    left, right, up, down = [np.zeros((H, W)) for _ in range(4)]
    for w in range(W):
        left[:, w] = (left[:, w-1] + 1) * field[:, w]
        right[:, -w-1] = (right[:, -w] + 1) * field[:, -w-1]
    for h in range(H):
        up[h, :] = (up[h-1, :] + 1) * field[h, :]
        down[-h-1, :] = (down[-h, :] + 1) * field[-h-1, :]
    s = left + right + up + down - 3
    print(int(np.max(s)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
h,w=map(int,input().split())
S=np.array([list(input()) for _ in range(h)])
S=np.where(S==".",1,0)

left,right,up,down=[np.zeros((h,w)) for _ in range(4)]
for i in range(w):
    left[:,i]=(left[:,i-1]+1)*S[:,i]
    right[:,-i-1]=(right[:,-i]+1)*S[:,-i-1]
for i in range(h):
    up[i]=(up[i-1]+1)*S[i]
    down[-i-1]=(down[-i]+1)*S[-i-1]

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

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 
def main():
    H, W = map(int, readline().split())
    G = np.zeros((H+2, W+2), np.int16)
    G[1:-1, 1:] = (np.frombuffer(read(H*(W+1)), dtype='B') == ord('.')).reshape((H, W+1))
    def solve(G):
        
        left = np.arange(G.shape[1], dtype=np.int16)*np.ones(G.shape, dtype=np.int16)
        left[G>0] = 0
        np.maximum.accumulate(left, out=left, axis=1)

        rG = G[..., ::-1]
        right = np.arange(G.shape[1], dtype=np.int16)*np.ones(G.shape, dtype=np.int16)
        right[rG>0] = 0
        np.maximum.accumulate(right, out=right, axis=1)

        right = G.shape[1] - right[..., ::-1]-1
        scoreres = (right-left-1) 
        scoreres[G==0] = 0
        return scoreres

    print((solve(G)+solve(G.T).T-1).max())
if __name__ == '__main__':
    main()

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 
def main():
    H, W = map(int, readline().split())
    G = np.zeros((H+2, W+2), np.int16)
    G[1:-1, 1:] = (np.frombuffer(read(H*(W+1)), dtype='B') == ord('.')).reshape((H, W+1))
    def solve(G):
        left = np.zeros(G.shape, np.int16)
        for i in range(G.shape[0]):
            left[i, ] = np.arange(G.shape[1])
        left[G>0] = 0
        np.maximum.accumulate(left, out=left, axis=1)

        rG = G[..., ::-1]
        right = np.zeros(G.shape, np.int16)
        for i in range(G.shape[0]): 
            right[i, ] = np.arange(G.shape[1])
        right[rG>0] = 0
        np.maximum.accumulate(right, out=right, axis=1)

        right = G.shape[1] - right[..., ::-1]-1
        scoreres = (right-left-1) 
        scoreres[G==0] = 0
        return scoreres

    print((solve(G)+solve(G.T).T-1).max())
if __name__ == '__main__':
    main()