Longest Contiguous Subsequence in a Grid

You are given a 2D grid of characters. Your task is to find the length of the longest contiguous subsequence of identical characters that appear in one of four directions: horizontally, vertically, or diagonally (both top‐left to bottom‐right and top‐right to bottom‐left).

The contiguous subsequence is defined as a sequence of adjacent cells in the grid where each cell contains the same character. Formally, if a cell at position \((i,j)\) is the start, then you should check in directions \((dx,dy)\) among \((0,1)\), \((1,0)\), \((1,1)\), and \((1,-1)\) until a different character is encountered or the grid boundary is reached. The answer is the maximum length among all possible sequences.

Note: The directions are illustrated using the LaTeX format: horizontally: \((0,1)\), vertically: \((1,0)\), diagonal down-right: \((1,1)\), and diagonal down-left: \((1,-1)\).

inputFormat

The first line of input contains two space-separated integers \(R\) and \(C\), representing the number of rows and columns in the grid, respectively.

This is followed by \(R\) lines, each containing a string of length \(C\) composed of characters.

outputFormat

Output a single integer, which is the length of the longest contiguous subsequence of identical characters in the grid, following the allowed directions.

5 5
ababa
bacab
abcba
bacab
ababa

3