#P10965. Largest Uniform Submatrix after Transformation

    ID: 13014 Type: Default 1000ms 256MiB

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