ICheckered field n × m. There are obstacles in some cells of the field. The obstacles completely occupy the cage.
The cannon can shoot in four directions: up, down, right or left, but cannot shoot over obstacles or stay in the same cage with an obstacle. All cells that it can shoot, including the one in which it is located, is considered an area of effect. Cells out of bounds are not counted. The size of the affected area is calculated as the number of cells in it.
Find the size of the maximum possible area of destruction of the cannon.
Field size n and m (1≤n, m≤2,000).
The next n lines contain the playing field. Each line consists of m characters “.” and “#”:
“.” means that the cell is free;
“#” Means that there is an obstacle in the cage.
It is guaranteed that there is at least one free cell.
n = int(input()) m = int(input()) board = [input() for i in range(n)] def get_map(board): f = [[len(j) for j in i.split('#')] for i in board] n = len(board) m = len(board) h_map = [[0 for _ in range(m)] for _ in range(n)] for i in range(n): s = 0 for j in f[i]: h_map[i][s:s+j] = [j]*(j) s = s+j+1 return h_map board_T = [''.join(i) for i in zip(*board)] # transpose h_map = get_map(board) v_map = get_map(board_T) v_map = [i for i in zip(*v_map)] # transpose res = max([max([v_map[i][j]+h_map[i][j] for j in range(m)]) for i in range(n)]) print(res-1)