Largest Square Subgrid

You are given a garden represented as a grid with n rows and m columns. Each cell of the grid contains either a flower ('F') or is empty ('E'). Your task is to determine the side length of the largest square subgrid that contains only flowers.

Formally, given a grid garden of size n \times m, find the maximum integer s such that there exists a square subgrid with side length s where every cell is equal to 'F'. The core recurrence used in the optimal solution is based on dynamic programming, expressed as: \[ dp[i][j] = \begin{cases} 1 & \text{if } i=0 \text{ or } j=0, \\ \min\{dp[i-1][j],\, dp[i][j-1],\, dp[i-1][j-1]\} + 1 & \text{if } garden[i][j]=='F', \end{cases} \] where \( dp[i][j] \) represents the side length of the largest square subgrid ending at cell \( (i,j) \). If no flower is present, then the value is 0.

If there is no 'F' in the grid (i.e. all cells are 'E'), then the answer is 0.

inputFormat

The input is given via standard input (stdin) with the following format:

n m
row1
row2
...
rown

Here, n and m are integers representing the number of rows and columns respectively. Each of the next n lines contains a string of length m made up of the characters 'F' and 'E'.

outputFormat

Output a single integer (to standard output, stdout) which is the side length of the largest square subgrid that contains only 'F'.

5 6
FFFEEF
FFFFFF
EEFFFF
FFFFFF
FFFFEF

3