Largest Uniform Flower Square

You are given a garden represented as a grid of size \(m \times n\). Each cell in the grid contains a flower, which is either a rose ('R') or a tulip ('T'). Your task is to determine the size of the largest square sub-grid in which all cells contain the same type of flower.

Dynamic Programming Hint: You can compute the answer using a DP approach where \(dp[i][j]\) represents the side length of the largest square ending at cell \((i, j)\) that has uniform flowers. The following recurrence can be used if the cell contains the desired character: \[ dp[i][j] = \min(dp[i-1][j],\ dp[i][j-1],\ dp[i-1][j-1]) + 1 \]

If the grid is empty or no square exists, output 0. Otherwise, output the length of the side of the largest square found.

inputFormat

The first line contains two integers \(m\) and \(n\), representing the number of rows and columns of the garden grid respectively. The following \(m\) lines each contain a string of length \(n\) consisting only of the characters 'R' and 'T', representing the garden.

outputFormat

Output a single integer which is the side length of the largest square sub-grid that contains only one type of flower.

3 3
RTR
TRT
RTR

1