Problem p03014 (python)

Fixed submission:
def solve2():
    H, W = [int(_) for _ in raw_input().split()]
    S = []
    for i in range(H):
        Si = [_ for _ in raw_input()]
        S.append(Si)
    L = [[0] * W for i in range(H)]
    R = [[0] * W for i in range(H)]
    D = [[0] * W for i in range(H)]
    U = [[0] * W for i in range(H)]
    # Left
    for i in range(H):
        if S[i][0] == '.':
            L[i][0] = 1
    for i in range(H):
        for j in range(1,W):
            if S[i][j] == '.':
                L[i][j] = L[i][j-1] + 1
            else:
                L[i][j] = 0
    # Right
    for i in range(H):
        if S[i][W-1] == '.':
            R[i][W-1] = 1
    for i in range(H):
        for j in range(W-2,-1,-1):
            if S[i][j] == '.':
                R[i][j] = R[i][j+1] + 1
            else:
                R[i][j] = 0
    # Down
    for j in range(W):
        if S[0][j] == '.':
            D[0][j] = 1
    for j in range(W):
        for i in range(1,H):
            if S[i][j] == '.':
                D[i][j] = D[i-1][j] + 1
            else:
                D[i][j] = 0
    # Up
    for j in range(W):
        if S[H-1][j] == '.':
            U[H-1][j] = 1
    for j in range(W):
        for i in range(H-2,-1,-1):
            if S[i][j] == '.':
                U[i][j] = U[i+1][j] + 1
            else:
                U[i][j] = 0
    ans = 1
    for i in range(H):
        for j in range(W):
            ans = max(ans, L[i][j] + R[i][j] + D[i][j] + U[i][j] - 3)
    print ans

if __name__ == '__main__':
    solve2()

Buggy submission (verdict: Runtime Error):
from collections import deque

def solve():
    H, W = [int(_) for _ in raw_input().split()]
    S = []
    for i in range(H):
        Si = [_ for _ in raw_input()]
        S.append(Si)
    rowm = [None] * H
    for i in range(H):
        start = -1
        end = 0
        save = (start, end, i)
        for j in range(W):
            if S[i][j] == '.':
                end = j
            else:
                start = j
                end = j
            if end - start > save[1] - save[0]:
                save = (start, end, i)
        rowm[i] = save
    colm = [None] * W
    for j in range(W):
        start = -1
        end = 0
        save = (start, end, j)
        for i in range(H):
            if S[i][j] == '.':
                end = i
            else:
                start = i
                end = i
            if end - start > save[1] - save[0]:
                save = (start, end, j)
        colm[j] = save
    rowm.sort(key = lambda x: x[1] - x[0], reverse = True)
    colm.sort(key = lambda x: x[1] - x[0], reverse = True)
    def max_ans(i,j):
        s1, e1, row = rowm[i]
        s2, e2, col = colm[j]
        return e1 - s1 + e2 - s2 - 1
    # priority queue
    ij_set = set()
    ij_set.add((0, 0))
    queue = deque()
    queue.append((max_ans(0, 0), 0,0))
    def AddToQueue(_ele):
        if len(queue) == 0:
            queue.append(_ele)
        else:
            cnt = 0
            while cnt < len(queue) and queue[cnt][0] >= _ele[0]:
                cnt += 1
            ij = (_ele[1], _ele[2])
            if not (ij in ij_set):
                queue.insert(cnt, _ele)
                ij_set.add(ij)
    ret = 1
    while len(queue) > 0:
        ans, i, j = queue.popleft()
        s1, e1, row = rowm[i]
        s2, e2, col = colm[j]
        if ans == 1:
            ret = ans
            break
        if row >= s2 and row <=e2 and col >= s1 and col <= e1:
            ret = ans
            break
        if i + 1 < H:
            AddToQueue((max_ans(i+1,j), i+1, j))
        if j + 1 < W:
            AddToQueue((max_ans(i,j+1), i, j+1))
    print ret

if __name__ == '__main__':
    solve()

Buggy submission (verdict: Runtime Error):
from collections import deque

def solve():
    H, W = [int(_) for _ in raw_input().split()]
    S = []
    for i in range(H):
        Si = [_ for _ in raw_input()]
        S.append(Si)
    rowm = [None] * H
    for i in range(H):
        start = -1
        end = 0
        save = (start, end, i)
        for j in range(W):
            if S[i][j] == '.':
                end = j
            else:
                start = j
                end = j
            if end - start > save[1] - save[0]:
                save = (start, end, i)
        rowm[i] = save
    colm = [None] * W
    for j in range(W):
        start = -1
        end = 0
        save = (start, end, j)
        for i in range(H):
            if S[i][j] == '.':
                end = i
            else:
                start = i
                end = i
            if end - start > save[1] - save[0]:
                save = (start, end, j)
        colm[j] = save
    rowm.sort(key = lambda x: x[1] - x[0], reverse = True)
    colm.sort(key = lambda x: x[1] - x[0], reverse = True)
    def max_ans(i,j):
        s1, e1, row = rowm[i]
        s2, e2, col = colm[j]
        return e1 - s1 + e2 - s2 - 1
    # priority queue
    ij_set = set()
    ij_set.add((0, 0))
    queue = deque()
    queue.append((max_ans(0, 0), 0,0))
    def AddToQueue(_ele):
        if len(queue) == 0:
            queue.append(_ele)
        else:
            cnt = 0
            while cnt < len(queue) and queue[cnt][0] >= _ele[0]:
                cnt += 1
            ij = (_ele[1], _ele[2])
            if not (ij in ij_set):
                queue.insert(cnt, _ele)
                ij_set.add(ij)
    ret = 1
    while len(queue) > 0:
        ans, i, j = queue.popleft()
        s1, e1, row = rowm[i]
        s2, e2, col = colm[j]
        if ans == 1:
            ret = ans
            break
        if row >= s2 and row <=e2 and col >= s1 and col <= e1:
            ret = ans
            break
        if i + 1 < H:
            AddToQueue((max_ans(i+1,j), i+1, j), queue, ij_set)
        if j + 1 < W:
            AddToQueue((max_ans(i,j+1), i, j+1), queue, ij_set)
    print ret

if __name__ == '__main__':
    solve()