#P10965. Largest Uniform Submatrix after Transformation
Largest Uniform Submatrix after Transformation
Largest Uniform Submatrix after Transformation
You are given an n x m matrix where each cell contains one of the letters from the set { 'a', 'b', 'c', 'w', 'x', 'y', 'z' }.
You are allowed to change some letters according to the following rules:
- 'w' can be changed to either 'a' or 'b'.
- 'x' can be changed to either 'b' or 'c'.
- 'y' can be changed to either 'a' or 'c'.
- 'z' can be changed to 'a', 'b' or 'c'.
Letters 'a', 'b', and 'c' are fixed and cannot be changed.
Your task is to determine the largest area of a contiguous rectangular submatrix (formed by consecutive rows and columns) where all characters are identical after optimally applying the allowed transformations.
inputFormat
The input begins with a line containing two space‐separated integers n and m indicating the dimensions of the matrix. This is followed by n lines, each containing a string of m characters (without spaces) representing the matrix.
outputFormat
Output a single integer representing the area (number of cells) of the largest uniform submatrix that can be achieved by applying the allowed letter transformations optimally.
sample
3 3
abc
wxy
zab
3