1.3 It's A Grid!
(RankList for this Question)
Score: 100pts
Time Limit: 1.00 sec
There is a \(N\) * \(M\) grid ( \(N\) is the number of rows and \(M\) number of columns). You are given \(N\) strings \(S_i\), consisting of ‘O’ indicating empty space and ‘X’ indicating obstacle, each of length \(M\).

Let us define a function \(f(i,j)\) for all the cells of the grid (\(i\) is the row number and \(j\) is the column number) as count of all the cells in up, down, left and right direction of the cell \((i,j)\) until an obstacle is reached in the respective direction. If the the cell \((i,j)\) is an obstacle then \(f(i,j)\) = 0. Read the sample cases for better understanding.

Find the maximum \(f(i,j)\) possible.

NOTE - Problem has tight time constraints. If you think you have an optimised code but the judge gave you a TLE verdict, you can try resubmitting a couple of times since the judge sometimes gives a higher absolute running time due to server idleness. In case you get a SIGKILL verdict or TLE multiple times, that would mean your approach is most probably not an optimal one.

Constraints
\(1 \leq N, M \leq 500 \)
\(1 \leq i \leq N\)
\(1 \leq j \leq M\)
\(S_i\) has length \(M\) and consists of only ‘O’ or ‘X’.
There is atleast one empty space ‘O’ in a given grid.

Input Format
\(N M\)
\(S_1\)
\(S_2\)
.
.
.
\(S_n\)

Output Format
Single integer - maximum value of \(f(i,j)\) possible.

Example 1
Input:
5 5
OOXOO
XXOXX
XOOOO
XOXOO
OXXXO

Output:
6

Explanation:
Here, if we consider 1-based indexing for the 2D grid we can see that maximum value will be of \(f(3,5) = 6\). It will include all the empty spaces in cardinal directions of \((3,5) ie (3,2), (3,3),(3,4),(3,5),(4,5),(5,5)\).

Example 2
Input:
5 4
OOXO
OXOX
XOOO
OOOX
XOXX

Output:
5

Explanation:
Here there are \(2\) cells present which have the maximum value for \(f(i,j)\). They are -
\(f(3,3) : (3,3),(3,2),(3,4),(2,3),(4,3)\) and
\(f(4,3) : (4,1),(4,2),(4,3),(3,4),(2,4)\)

Log In to solve the Question