Problem p03014 (python)

Fixed submission:
#上下方向の探索と左右方向の探索をまとめる
#まず表を完成させる-->全マスの探索
H, W = map(int, input().split())
lst = [['#'] * (W+2)]
lst += [['#'] + list(input()) + ['#'] for i in range(H)]
lst += [['#'] * (W+2)]


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

for i in range(1, H+1):
    for j in range(1, W+1):
        lst_hidari[i][j] = 0 if lst[i][j] == '#' else 1 + lst_hidari[i][j-1]
    for j in range(W, 0, -1):
        lst_migi[i][j] = 0 if lst[i][j] == '#' else 1 + lst_migi[i][j+1]

for j in range(1, W+1):
    for i in range(1, H+1):
        lst_ue[i][j] = 0 if lst[i][j] == '#' else 1 + lst_ue[i-1][j]
    for i in range(H+1, 0, -1):
        lst_shita[i][j] = 0 if lst[i][j] == '#' else 1 + lst_shita[i+1][j]

ans = 0
for i in range(1,H+1):
    for j in range(1, W+1):
        ans = max(ans, lst_ue[i][j]+lst_shita[i][j]+lst_migi[i][j]+lst_hidari[i][j]-3)

print (ans)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 9)

import functools
@functools.lru_cache(maxsize = None)

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

    u_table = [[-1] * (W + 2) for _ in range(W + 2)]
    d_table = [[-1] * (W + 2) for _ in range(W + 2)]
    r_table = [[-1] * (W + 2) for _ in range(W + 2)]
    l_table = [[-1] * (W + 2) for _ in range(W + 2)]

    def u(i, j): #up方向に何マス光が伸びるかを数える
        if u_table[i][j] != -1:
            return u_table[i][j]
        if lst[i][j] == '#':
            u_table[i][j] = 0
            return 0
        else:
            u_table[i][j] = u(i - 1, j) + 1
            return u_table[i][j]
    
    def d(i, j):
        if d_table[i][j] != -1:
            return d_table[i][j]
        if lst[i][j] == '#':
            d_table[i][j] = 0
            return 0
        else:
            d_table[i][j] = d(i + 1, j) + 1
            return d_table[i][j]
    
    def r(i, j):
        if r_table[i][j] != -1:
            return r_table[i][j]
        if lst[i][j] == '#':
            r_table[i][j] = 0
            return 0
        else:
            r_table[i][j] = r(i, j + 1) + 1
            return r_table[i][j]

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

    #スタートマスを変えながら最大の範囲の広さを検索
    ans = 0
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            if lst[i][j] == '.': #光源を置く場所が障害物でないとき
                tmp = u(i, j) + d(i, j) + r(i, j) + l(i, j) - 3
                # print ('(i, j) = ', i, j, tmp)
                ans = max(ans, tmp)
    print (ans)
    return 

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 9)

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

    u_table = [[-1] * (W + 2) for _ in range(W + 2)]
    d_table = [[-1] * (W + 2) for _ in range(W + 2)]
    r_table = [[-1] * (W + 2) for _ in range(W + 2)]
    l_table = [[-1] * (W + 2) for _ in range(W + 2)]

    def u(i, j): #up方向に何マス光が伸びるかを数える
        if u_table[i][j] != -1:
            return u_table[i][j]
        if lst[i][j] == '#':
            u_table[i][j] = 0
            return 0
        else:
            u_table[i][j] = u(i - 1, j) + 1
            return u_table[i][j]
    
    def d(i, j):
        if d_table[i][j] != -1:
            return d_table[i][j]
        if lst[i][j] == '#':
            d_table[i][j] = 0
            return 0
        else:
            d_table[i][j] = d(i + 1, j) + 1
            return d_table[i][j]
    
    def r(i, j):
        if r_table[i][j] != -1:
            return r_table[i][j]
        if lst[i][j] == '#':
            r_table[i][j] = 0
            return 0
        else:
            r_table[i][j] = r(i, j + 1) + 1
            return r_table[i][j]

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

    #スタートマスを変えながら最大の範囲の広さを検索
    ans = 0
    for i in range(1, H + 1):
        for j in range(1, W + 1):
            if lst[i][j] == '.': #光源を置く場所が障害物でないとき
                tmp = u(i, j) + d(i, j) + r(i, j) + l(i, j) - 3
                # print ('(i, j) = ', i, j, tmp)
                ans = max(ans, tmp)
    print (ans)
    return 

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(3000)

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
if H < 1500 and W < 1500:
    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)
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)

Buggy submission (verdict: Runtime Error):
import sys

sys.setrecursionlimit(3000)

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
if H < 1500 and W < 1500:
    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)
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 (asn)
                    sys.exit()

print (ans)

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


# print (lst)
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]        

# def shita(i, j):
#     count = 0
#     for k in range(1, H+1):
#         if lst[i+k][j] == '#':
#             return count
#         else:
#             count += 1

# def hidari(i, j):
#     count = 0
#     for k in range(1,W+1):
#         if lst[i][j-k] == '#':
#             return count
#         else:
#             count += 1

# def migi(i, j):
#     count = 0
#     for k in range(1,W+1):
#         if lst[i][j+k] == '#':
#             return count
#         else:
#             count += 1

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

print (ans)
# print (lst_ue)