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: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        cnt = 1
        a = i
        b = j
        while a+1 <= H-1:
            if S[a+1][b] == '#':
                break
            cnt += 1
            a += 1
        a = i
        while a-1 >= 0:
            if S[a-1][b] == '#':
                break
            cnt += 1
            a -= 1
        a = i
        b = j
        while b+1 <= W-1:
            if S[a][b+1] == '#':
                break
            cnt += 1
            b += 1
        b = j
        while b-1 >= 0:
            if S[a][b-1] == '#':
                break
            cnt += 1
            b -= 1
        ans = max(ans, cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

S = [None] * H
ans = np.zeros((H, W))

for i in range(H):
    s_tmp = [-1] * W
    s = input()
    for j, c in enumerate(s):
        if c == "#":
            s_tmp[j] = 1
        else:
            s_tmp[j] = 0
    S[i] = s_tmp

max_tmp = 0
coord = (-1, -1)
for i in range(H):
    # 左から右
    tmp = 0
    for j in range(W):
        if S[i][j] == 1:
            tmp = 0
        else:
            tmp += 1
        ans[i, j] += tmp
    # 右から左
    tmp = 0
    for j in reversed(range(W)):
        if S[i][j] == 1:
            tmp = 0
        else:
            tmp += 1
        ans[i, j] += tmp

# 右から左
for i in range(W):
    # 上から下
    tmp = 0
    for j in range(H):
        if S[j][i] == 1:
            tmp = 0
        else:
            tmp += 1
        ans[j, i] += tmp
    # 下から上
    tmp = 0
    for j in reversed(range(H)):
        if S[j][i] == 1:
            tmp = 0
        else:
            tmp += 1
        ans[j, i] += tmp
        if ans[j, i] > max_tmp:
            max_tmp = ans[j, i]
            coord = (j, i)

score = 1

tmp_x = coord[1]
while True:
    tmp_x -= 1
    if tmp_x < 0:
        break
    if S[coord[0]][tmp_x] == 0:
        score += 1
    else:
        break
tmp_x = coord[1]
while True:
    tmp_x += 1
    if tmp_x >= W:
        break
    if S[coord[0]][tmp_x] == 0:
        score += 1
    else:
        break
tmp_y = coord[0]
while True:
    tmp_y -= 1
    if tmp_y < 0:
        break
    if S[tmp_y][coord[1]] == 0:
        score += 1
    else:
        break
tmp_y = coord[0]
while True:
    tmp_y += 1
    if tmp_y >= H:
        break
    if S[tmp_y][coord[1]] == 0:
        score += 1
    else:
        break

print(score)

Submission status: Time Limit Exceeded

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

S = [['x']*W]*H

for h in range(H):
    S[h] = list(input())
#print(S)

for h in range(H):
    bw, sw = 0,0
    for i in range(W):
        if S[h][i] != '#' and i != W-1:
            bw += 1
        elif S[h][i] == '#':
            for asw in range(sw, i):
                S[h][asw] = bw
            bw = 0
            sw = i+1
            #print(sw,bw)
        elif i == W-1:
            bw += 1
            #print('err')
            for asw in range(sw, W):
                S[h][asw] = bw
#print('2nd')
#print(S)
for w in range(W):
    bh, sh = 0,0
    for i in range(H):
        if S[i][w] != '#' and i != H-1:
            bh += 1
        elif S[i][w] == '#':
            for ash in range(sh, i):
                S[ash][w] += bh
            bh = 0
            sh = i+1
            #print(sh,bh)
        elif i == H-1:
            bh += 1
            #print('err')
            for ash in range(sh, H):
                S[ash][w] += bh

#print(S)

r = 0
for s in S:
    for As in set(s):
        if str(As).isdecimal():
            r = max(r, As)
print(r-1)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
x = [list(input()) for _ in range(h)]
xt = [[x[i][j] for i in range(h)] for j in range(w)]
xh = [[0 for i in range(h)] for j in range(w)]
for i, xi in enumerate(x):
    l = 0
    for j, xij in enumerate(xi):
        if xij == '#':
            for k in range(l, j):
                xh[k][i] = j - l
            l = j + 1
    for k in range(l, w):
        xh[k][i] = w - l

ans = 0
for i, xi in enumerate(xt):
    l = 0
    xhi = xh[i]
    for j, xij in enumerate(xi):
        if xij == '#':
            if j > l:
                ans = max(ans, max(xhi[l:j]) + j - l - 1)
            l = j + 1
    if h > l:
        ans = max(ans, max(xhi[l:]) + h - l - 1)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

def aaa(s):
    if type(s) == type([]):
        s = ''.join(s)
    i = 0
    l = len(s)
    o = []
    while True:
        if i == l:
            break
        if s[i] == ".":
            n = 0
            while i < l and s[i] == '.':
                i += 1
                n += 1
            o.append(itertools.repeat(n,n))
        else:
            o.append([0])
            i += 1
    return itertools.chain.from_iterable(o)

Hor = [0]*H
for y in range(H):
    Hor[y] = list(aaa(S[y]))

Ver = [0]*W
for x in range(W):
    Ver[x] = list(aaa([S[_][x] for _ in range(H)]))

ans = 1
for x,y in itertools.product(range(W),range(H)):
    h = Hor[y][x]
    v = Ver[x][y]
    ans = max(ans,h+v-1)

print(ans)

Submission status: Time Limit Exceeded

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

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

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

for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            continue
        # up
        if h-1 < 0 or S[h-1][w] == '#':
            b[h][w][0] = 0
        else:
            b[h][w][0] = b[h-1][w][0] + 1
        # left
        if w-1 < 0 or S[h][w-1] == '#':
            b[h][w][1] = 0
        else:
            b[h][w][1] = b[h][w-1][1] + 1

for h in range(H-1, -1, -1):
    for w in range(W-1, -1, -1):
        if S[h][w] == '#':
            continue
        # down
        if h+1 >= H or S[h+1][w] == '#':
            b[h][w][2] = 0
        else:
            b[h][w][2] = b[h+1][w][2] + 1
        # right
        if w+1 >= W or S[h][w+1] == '#':
            b[h][w][3] = 0
        else:
            b[h][w][3] = b[h][w+1][3] + 1

#for h in range(H):
#    print(b[h])
ans = 0
for h in range(H):
    for w in range(W):
        if S[h][w] == '#':
            continue
        tmp = sum(b[h][w]) + 1
        if tmp > ans:
            ans = tmp

print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = [int(x) for x in input().split(' ')]
S = []
for i in range(H):
    S.append(input())
max_count = 0
for ix in range(W):
    for iy in range(H):
        if S[iy][ix] == '#':
            continue
        if S[iy].count('.') + H < max_count:
            continue
        vlist = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        sum = 1 # self
        for v in vlist:
            x, y = ix, iy
            while True:
                x += v[0]
                y += v[1]
                if not ((0 <= x <= W - 1) and (0 <= y <= H - 1)):
                    break
                if S[y][x] == "#":
                    break
                sum += 1
        max_count = max(max_count, sum)
print(max_count)

Submission status: Time Limit Exceeded

Solution code:
import bisect
from operator import itemgetter
import math
import functools
import itertools
import numpy as np
import sys
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def tamiL(x,y,n):
  if (0 <= x < W) and (0 <= y < H):
    if grid[y][x] == ".":
      return tamiL(x-1,y,n+1)
    else:
      return n
  else:
    return n

def tamiR(x,y,n):
  if (0 <= x < W) and (0 <= y < H):
    if grid[y][x] == ".":
      return tamiR(x+1,y,n+1)
    else:
      return n
  else:
    return n

def tamiU(x,y,n):
  if (0 <= x < W) and (0 <= y < H):
    if grid[y][x] == ".":
      return tamiU(x,y-1,n+1)
    else:
      return n
  else:
    return n

def tamiD(x,y,n):
  if (0 <= x < W) and (0 <= y < H):
    if grid[y][x] == ".":
      return tamiD(x,y+1,n+1)
    else:
      return n
  else:
    return n

H,W = IL()
grid = [[i for i in S()] for i in range(H)]

ans = 0
for i in range(H):
  for j in range(W):
    if grid[i][j] == ".":
      cnt = 0
      cnt += tamiL(j-1,i,0)
      cnt += tamiR(j+1,i,0)
      cnt += tamiU(j,i-1,0)
      cnt += tamiD(j,i+1,0)
      ans = max(ans,cnt+1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
h, w = map(int, input().split())
maze = []
for hh in range(h):
  row = list(input())
  maze.append(row)
#print(maze)
hscore = []
for hh in range(h):
  hrow = [0] * w
  for ww in range(w):
    if ww == 0:
      if maze[hh][ww] == '.':
        hrow[ww] = 1
      else:
        hrow[ww] = 0
    else:
      if maze[hh][ww] == '.':
        hrow[ww] = hrow[ww-1] + 1
      else:
        hrow[ww] = 0
  for ww in reversed(range(w)):
    if ww != w-1:
      if maze[hh][ww] == '#':
        hrow[ww] = 0
      elif maze[hh][ww+1] == '.':
        hrow[ww] = hrow[ww+1]

  hscore.append(hrow)

# transpose
#print(hscore)
maze_t = list(map(list, zip(*maze)))
vscore = []

h, w = w, h

for hh in range(h):
  hrow = [0] * w
  for ww in range(w):
    if ww == 0:
      if maze_t[hh][ww] == '.':
        hrow[ww] = 1
      else:
        hrow[ww] = 0
    else:
      if maze_t[hh][ww] == '.':
        hrow[ww] = hrow[ww-1] + 1
      else:
        hrow[ww] = 0
  for ww in reversed(range(w)):
    if ww != w-1:
      if maze_t[hh][ww] == '#':
        hrow[ww] = 0
      elif maze_t[hh][ww+1] == '.':
        hrow[ww] = hrow[ww+1]
  vscore.append(hrow)

vscore = list(map(list, zip(*vscore)))

h, w = w, h

max_score = 0
for hh in range(h):
  for ww in range(w):
    score = hscore[hh][ww] + vscore[hh][ww] - 1
    max_score = max([max_score, score])
print(max_score)

Submission status: Time Limit Exceeded

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

	#上下左右
	STAGE_score = []

	result = 0
	for y in range(H):
		count, score = 0, []
		for x in range(W):
			if STAGE[y][x] == ".":
				count += 1
				if x == W - 1:
					score += [count] * count
			else:
				if 0 < count:
					score += [count] * count
				score += [0]
				count = 0
		STAGE_score += [score]

	#for l in STAGE_score:
	#	print(*l)

	for y in range(H):
		for x in range(W):
			if STAGE[y][x] == "#":
				continue
			else:
				score = STAGE_score[y][x]
				for n in range(y - 1, -1, -1):
					if STAGE[n][x] == "#":
						break
					else:
						score += 1
				for n in range(y + 1, H):
					if STAGE[n][x] == "#":
						break
					else:
						score += 1
			result = max(result, score)
			#print(y, x, result)

	print(result)
main()

Submission status: Time Limit Exceeded

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

up = [[0]*w for _ in range(h)]
for w_i in range(w):
    if s[0][w_i] == '#':
        pass
    else:
        up[0][w_i] = 1
for h_i in range(1, h):
    for w_j in range(w):
        if s[h_i][w_j] == '#':
            pass
        else:
            up[h_i][w_j] = up[h_i-1][w_j] + 1
# print(up)

down = [[0]*w for _ in range(h)]
for w_i in range(w):
    if s[-1][w_i] == '#':
        pass
    else:
        down[-1][w_i] = 1
for h_i in range(h-1)[::-1]:
    for w_j in range(w):
        if s[h_i][w_j] == '#':
            pass
        else:
            down[h_i][w_j] = down[h_i+1][w_j] + 1
# print(down)

left = [[0]*w for _ in range(h)]
for h_i in range(h):
    if s[h_i][0] == '#':
        pass
    else:
        left[h_i][0] = 1
for h_i in range(h):
    for w_j in range(1,w):
        if s[h_i][w_j] == '#':
            pass
        else:
            left[h_i][w_j] = left[h_i][w_j-1] + 1
# print(left)

right = [[0]*w for _ in range(h)]
for h_i in range(h):
    if s[h_i][-1] == '#':
        pass
    else:
        right[h_i][-1] = 1
for h_i in range(h):
    for w_j in range(w-1)[::-1]:
        if s[h_i][w_j] == '#':
            pass
        else:
            right[h_i][w_j] = right[h_i][w_j+1] + 1
# print(right)

num = [[0]*w for _ in range(h)]
for h_i in range(h):
    for w_j in range(w):
        num[h_i][w_j] += up[h_i][w_j] + down[h_i][w_j] + left[h_i][w_j] + right[h_i][w_j] - 4 + 1
# print(num)

ans = max([max(i) for i in num])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(list(input()))
    
## 横方向につながっているか
yoko = [0]*(H*W)
for i in range(H):
  hold = 0
  for j in range(W):
    if S[i][j] == '#':
      hold = 0
    else:
      hold += 1
      yoko[i*W+j] = hold
  ## 今度は逆順に辿る
  hold = 0
  for j in range(W):
    if S[i][W-1-j] == '#':
      hold = 0
    else:
      hold = max(hold, yoko[i*W+(W-1-j)])
      yoko[i*W+(W-1-j)] = hold
      
## 縦方向につながっているか
tate = [0]*(H*W)
for j in range(W):
  hold = 0
  for i in range(H):
    if S[i][j] == '#':
      hold = 0
    else:
      hold += 1
      tate[i*W+j] = hold
  ## 今度は逆順に辿る
  hold = 0
  for i in range(H):
    if S[H-1-i][j] == '#':
      hold = 0
    else:
      hold = max(hold, tate[(H-1-i)*W+j])
      tate[(H-1-i)*W+j] = hold
      
solver = []
for i in range(H):
  for j in range(W):
    if S[i][j] == '#':
      continue
    else:
      var = yoko[i*W+j] + tate[i*W+j] - 1
      solver.append(var)

print(max(solver))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

light = np.array([[-1, -1] for _ in range(H*W)])

for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        
        if light[W*i+j][0] == -1:
            tmp = 0
            tate = i
            while tate < H and S[tate][j] == '.':
                tmp += 1
                tate += 1
            for k in range(tmp):
                light[W*(i+k)+j][0] = tmp
        
        if light[W*i+j][1] == -1:
            tmp = 0
            yoko = j
            while yoko < W and S[i][yoko] == '.':
                tmp += 1
                yoko += 1
            for k in range(tmp):
                light[W*i+j+k][1] = tmp


print(np.max(light.sum(axis=1))-1)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(h):
  for j in range(w):
    u = 0 #上方向
    d = 0 #下方向
    l = 0 #左方向
    r = 0 #右方向
    if s[i][j] == ".":
      x = j
      y = i
      check = 0
      while y > 0 and check == 0: #上方向
        if s[y-1][x] == ".":
          u += 1
          y -= 1
        else:
          check += 1
      x = j
      y = i
      check = 0
      while y < h-1 and check == 0: #下方向
        if s[y+1][x] == ".":
          d += 1
          y += 1
        else:
          check += 1
      x = j
      y = i
      check = 0
      while x < w-1 and check == 0: #右方向
        if s[y][x+1] == ".":
          r += 1
          x += 1
        else:
          check += 1
      x = j
      y = i
      check = 0
      while x > 0 and check == 0: #左方向
        if s[y][x-1] == ".":
          l += 1
          x -= 1
        else:
          check += 1
    if ans < u+d+r+l:
      ans = u+d+r+l
print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)

H, W = map(int, input().split())
lst = [['#'] * (W+2)]
lst += [['#'] + list(input()) + ['#'] for i in range(H)]
lst += [['#'] * (W+2)]


lst_ue = [[-1] * (W+2) for i in range(H+2)]
lst_shita = [[-1] * (W+2) for i in range(H+2)]
lst_migi = [[-1] * (W+2) for i in range(H+2)]
lst_hidari = [[-1] * (W+2) for i in range(H+2)]

# print (lst_ue)
def ue(i, j):
    if lst_ue[i][j] != -1:
        return lst_ue[i][j]
    if lst[i][j] == '#':
        lst_ue[i][j] = 0
        return 0
    else:
        lst_ue[i][j] = ue(i-1, j) + 1
        return lst_ue[i][j]


def shita(i, j):
    if lst_shita[i][j] != -1:
        return lst_shita[i][j]
    if lst[i][j] == '#':
        lst_shita[i][j] = 0
        return 0
    else:
        lst_shita[i][j] = shita(i+1, j) + 1
        return lst_shita[i][j]        


def hidari(i, j):
    if lst_hidari[i][j] != -1:
        return lst_hidari[i][j]
    if lst[i][j] == '#':
        lst_hidari[i][j] = 0
        return 0
    else:
        lst_hidari[i][j] = hidari(i, j-1) + 1
        return lst_hidari[i][j]        

def migi(i, j):
    if lst_migi[i][j] != -1:
        return lst_migi[i][j]
    if lst[i][j] == '#':
        lst_migi[i][j] = 0
        return 0
    else:
        lst_migi[i][j] = migi(i, j+1) + 1
        return lst_migi[i][j]        

ans = 0
for i in range(1,H+1):
    for j in range(1, W+1):
        if lst[i][j] != '#':
            ans = max(ans, ue(i,j)+shita(i,j)+hidari(i,j)+migi(i,j)-3)
            if ans == H + W -1:
                print (ans)
                sys.exit()
# else:
#     for i in range(750,1250):
#         for j in range(750, 1250):
#             if lst[i][j] != '#':
#                 ans = max(ans, ue(i,j)+shita(i,j)+hidari(i,j)+migi(i,j)-3)
#                 if ans == H+W-1:
#                     print (ans)
#                     sys.exit()

print (ans)

Submission status: Time Limit Exceeded

Solution code:

import sys
import copy
input = sys.stdin.readline

h, w = [ int(v) for v in input().split() ]

field = [ list(map(int,input().replace("#","0").replace(".","1").replace("\n",""))) for i in range(h)]

yoko = [ copy.deepcopy(field[i]) for i in range(h)]


for i in range(h):
	for j in range(1,w):
		if yoko[i][j] == 0:
			yoko[i][j] = 0
		else:
			yoko[i][j] += yoko[i][j-1]
	for j in range(w-1,0,-1):
		if yoko[i][j-1] != 0:
			yoko[i][j-1] = max(yoko[i][j-1],yoko[i][j])

tate = [ [ field[i][j] for i in range(h)] for j in range(w) ]

for i in range(w):
	for j in range(1,h):
		if tate[i][j] == 0:
			tate[i][j] = 0
		else:
			tate[i][j] += tate[i][j-1]
	for j in range(h-1,0,-1):
		if tate[i][j-1] != 0:
			tate[i][j-1] = max(tate[i][j-1],tate[i][j])


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

print(ans-1)

Submission status: Time Limit Exceeded

Solution code:
#
import sys
import math
import numpy as np
import itertools

# いくつか入力
h,w = (int(i) for i in input().split())  

# 2次元配列
grid = []
for i in range(h):
    array = list(input())
    grid.append(array)

a = np.zeros((h,w), dtype=np.int)
#print(yoko)
b = np.zeros((h,w), dtype=np.int)
for i in range(h):
    for j in range(w):
        if grid[i][j]=='#':
            b[i][j] = 1
        else:
            b[i][j] = 0

for i in range(h):
    temp = 0
    for j in range(w):
        if b[i][j]==1:
            temp=0
        else:
            temp += 1
            a[i][j] += temp

for i in range(h):
    temp = 0
    for j in range(w-1,-1,-1):
        if b[i][j]==1:
            temp=0
        else:
            temp += 1
            a[i][j] += temp
#print(a)
for j in range(w):
    temp = 0
    for i in range(h):
        if b[i][j]==1:
            temp=0
        else:
            temp += 1
            a[i][j] += temp

for j in range(w):
    temp = 0
    for i in range(h-1,-1,-1):
        if b[i][j]==1:
            temp=0
        else:
            temp += 1
            a[i][j] += temp
answer=3
for i in range(h):
    for j in range(w):
        answer=max(a[i][j],answer)
#print(a)
print(answer-3)

Submission status: Time Limit Exceeded

Solution code:
h,w=(int(i) for i in input().split())
a=[]
b=[]
p=[]
for i in range(h):
  s=input()
  r=[]
  c=0
  for j in range(w):
    if s[j]==".":
      c=c+1
      if j==w-1:
        for k in range(c):
          r.append(c)
    elif s[j]=="#":
      for k in range(c):
        r.append(c)
      r.append(0)
      c=0
  a.append(r)
for i in range(w):
  r=[]
  c=0
  for j in range(h):
    if a[j][i]!=0:
      c=c+1
      if j==h-1:
        for k in range(c):
          r.append(c)
    elif a[j][i]==0:
      for k in range(c):
        r.append(c)
      r.append(0)
      c=0
  b.append(r)
for i in range(h):
  for j in range(w):
    p.append(a[i][j]+b[j][i]-1)
p.sort()
print(p[-1])

Submission status: Time Limit Exceeded

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

H, W = map(int, input().split())
maze = [input() for i in range(H)]
ans = 0

def search1(x, y, cnt):
    global ans
    if x < 0 or W <= x or y < 0 or H <= y or maze[y][x] == '#':
        ans += cnt - 1
        return

    search1(x + 1, y, cnt + 1)
    return
def search2(x, y, cnt):
    global ans
    if x < 0 or W <= x or y < 0 or H <= y or maze[y][x] == '#':
        ans += cnt - 1
        return

    search2(x - 1, y, cnt + 1)
    return
def search3(x, y, cnt):
    global ans
    if x < 0 or W <= x or y < 0 or H <= y or maze[y][x] == '#':
        ans += cnt - 1
        return

    search3(x, y + 1, cnt + 1)
    return
def search4(x, y, cnt):
    global ans
    if x < 0 or W <= x or y < 0 or H <= y or maze[y][x] == '#':
        ans += cnt - 1
        return

    search4(x, y - 1, cnt + 1)
    return

MAX = 0
for i in range(H):
    for j in range(W):
        if maze[i][j] == '#':
            continue
        search1(j, i, 0)
        search2(j, i, 0)
        search3(j, i, 0)
        search4(j, i, 0)
        MAX = max(ans + 1, MAX)
        ans = 0

print(MAX)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
H, W = map(int, input().split())
S = deque([])
L = deque([])
for i in range(H):
	s = list(input())
	S.append(s)
	l = deque([])
	count = 0
	for i in range(W):
		if s[i] == '#':
			for k in range(count):
				l.append(count)
			count = 0
			l.append(0)
		else:
			count += 1
	for k in range(count):
		l.append(count)
	L.append(l)
for i in range(W):
	count = 0
	for k in range(H):
		if L[k][i] == 0:
			for j in range(count):
				L[k - j - 1][i] += count
			count = 0
		else:
			count += 1
	for j in range(count):
		L[k - j - 1][i] += count			
ans = 0
for i in range(H):
	ans = max(max(L[i]) - 1, ans)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
H,W=(int(x) for x in input().split())
LL=[]
for i in range(H):
    L=[]
    S=input()
    for o in S.split('#'):
        L+=[len(o)]*len(o)
        L.append(0)
    LL.append(L[:W])

mx1=0
mx2=0
nLL=np.array(LL)
TnLL=nLL.T
for nL in TnLL:
    mx1=0
    count=0
    for a in nL:
        mx1=max(a,mx1)
        if a==0:
            mx2=max(mx2,mx1+count)
            count=0
            mx1=0
        else:
            count+=1
    mx2=max(mx2,mx1+count)
print(mx2-1)

Submission status: Time Limit Exceeded

Solution code:
import copy

H, W = map(int, input().split())
state = []
for i in range(H):
    row_list = list(input())
    state.append(row_list)


def light(row, col, state):
    col1 = copy.copy(col)
    next = '.'
    while next == '.':
        state[row][col1] = '+'
        col1 += 1
        if col1 >= W:
            break
        next = state[row][col1]
    
    col2 = copy.copy(col)
    next = '.'
    while next == '.':
        state[row][col2] = '+'
        col2 -= 1
        if col2 < 0:
            break
        next = state[row][col2]
    
    row1 = copy.copy(row)
    next = '.'
    while next == '.':
        state[row1][col] = '+'
        row1 += 1
        if row1 >= H:
            break
        next = state[row1][col]
    
    row2 = copy.copy(row)
    next = '.'
    while next == '.':
        state[row2][col] = '+'
        row2 -= 1
        if row2 < 0:
            break
        next = state[row2][col]
    
    return state


def lighted_fun(state):
    blank_list = []
    for h in range(H):
        for w in range(W):
            if state[h][w] == '+':
                blank_list.append([h, w])
    return blank_list


def blank_fun(state):
    blank_list = []
    for h in range(H):
        for w in range(W):
            if state[h][w] == '.':
                blank_list.append([h, w])
    return blank_list


blank_list = blank_fun(state)
blank_count = 0
for blank in blank_list:
    row = blank[0]
    col = blank[1]
    c_state = copy.deepcopy(state)
    lighted_state = light(row, col, c_state)
    blank_count_now = len(lighted_fun(lighted_state))
    if blank_count_now > blank_count:
        blank_count = blank_count_now


print(blank_count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


R, C = map(int, input().split())
F = []
R_light = np.zeros((R, C), np.int)
C_light = np.zeros((R, C), np.int)

for i in range(R):
    s = input()
    F.append(s)
    count_dot = 0
    c_right = 0
    c_left = 0
    while c_right < C:
        if s[c_right] == ".":
            count_dot += 1
            c_right += 1
        else:
            for c in range(c_left, c_right):
                R_light[i][c] = count_dot
            count_dot = 0
            c_left = c_right + 1
            c_right += 1

    if s[-1] == ".":
        for c in range(c_left, C):
            R_light[i][c] = count_dot


for j in range(C):
    s = "".join([F[i][j] for i in range(R)])
    count_dot = 0
    r_below = 0
    r_above = 0
    while r_below < R:
        if s[r_below] == ".":
            count_dot += 1
            r_below += 1
        else:
            for r in range(r_above, r_below):
                C_light[r][j] = count_dot
            count_dot = 0
            r_above = r_below + 1
            r_below += 1

    if s[-1] == ".":
        for r in range(r_above, R):
            C_light[r][j] = count_dot

F = R_light + C_light
print(np.max(F) - 1)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
H, W = map(int, input().split())
s = [input() for i in range(H)]

def length(index, block_idx, full_length):
    if len(block_idx) == 0:
        return full_length
    idx = bisect_left(block_idx, index)
    if idx == len(block_idx):
        return full_length - index
    return block_idx[idx] - index

rows = []

for i in range(H):
    row = []
    block_idx = []
    for k in range(len(s[i])):
        if s[i][k] == "#":
            block_idx.append(k)

    for j in range(W):
        if j == 0:
            if s[i][0] == "#":
                row.append(0)
            else:
                l = length(0, block_idx, W)
                row.append(l)
        else:
            if s[i][j] == "#":
                row.append(0)
            else:
                if s[i][j-1] != "#":
                    row.append(row[len(row)-1])
                else:
                    l = length(j, block_idx, W)
                    row.append(l)
    rows.append(row)

columns = []

for i in range(W):
    column = []

    _s = ""
    block_idx = []
    for k in range(H):
        _s += s[k][i]
        if s[k][i] == "#":
            block_idx.append(k)

    for j in range(H):
        if j == 0:
            if _s[0] == "#":
                column.append(0)
            else:
                l = length(0, block_idx, H)
                column.append(l)
        else:
            if _s[j] == "#":
                column.append(0)
            else:
                if _s[j - 1] != "#":
                    column.append(column[len(column) - 1])
                else:
                    l = length(j, block_idx, H)
                    column.append(l)
    columns.append(column)

res = []
max_score = 0
for i in range(H):
    for j in range(W):
        r = rows[i][j]
        c = columns[j][i]
        score = r + c - 1
        if max_score < score:
            max_score = score
print(max_score)

Submission status: Time Limit Exceeded

Solution code:
def count_light(i, j):
  count = 1
  
  # 上方向
  k = i - 1
  while k >= 0:
    if S[k][j] == '.':
      count += 1
    else:
      break
    k -= 1
  
  # 下方向
  k = i + 1
  while k < H:
    if S[k][j] == '.':
      count += 1
    else:
      break
    k += 1
  
  # 右方向
  k = j + 1
  while k < W:
    if S[i][k] == '.':
      count += 1
    else:
      break
    k += 1
  
  # 左方向
  k = j - 1
  while k >= 0:
    if S[i][k] == '.':
      count += 1
    else:
      break
    k -= 1
  
  return count
    
H,W = (int(x) for x in input().split())
S = []
for i in range(H):
  S.append(list(input()))

max = 0
for i in range(H):
  for j in range(W):
    if not(S[i][j] == '#'):
      tmp = count_light(i, j)
      if (max < tmp):
        max = tmp

print(max)

Submission status: Time Limit Exceeded

Solution code:
H, W = map(int, input().split())
S = [0 for i in range(H)]
for i in range(H):
    S[i] = input()
T = ['' for j in range(W)]
for j in range(W):
    for i in range(H):
        T[j] += S[i][j]
#print(T)
yoko = [[0 for j in range(W)] for i in range(H)]
tate = [[0 for j in range(W)] for i in range(H)]
for i in range(H):
    idx = [j for j, x in enumerate(S[i]) if x == '#']
    idx.append(W)
    count = 0
    for j in range(W):
        if j == idx[count]:
            count += 1
        else:
            if count >= 1:
                yoko[i][j] = idx[count] - idx[count-1] - 1
            else:
                yoko[i][j] = idx[count]

for j in range(W):
    idx = [i for i, x in enumerate(T[j]) if x == '#']
    idx.append(H)
    count = 0
    for i in range(H):
        if i == idx[count]:
            count += 1
        else:
            if count >= 1:
                tate[i][j] = idx[count] - idx[count-1] - 1
            else:
                tate[i][j] = idx[count]
maxdp = 0
for i in range(H):
    for j in range(W):
        maxdp = max(maxdp, tate[i][j] + yoko[i][j]-1)
print(maxdp)

#print(yoko)
#print(tate)