Taco Puzzle: Maximum Blocks Eliminated

You are given a grid representing a puzzle. Each cell in the grid contains a non-negative integer. A positive integer represents a colored block while 0 represents an empty cell. Your task is to draw one valid line in one of the following four directions: horizontal (right), vertical (down), diagonal (down-right), or anti-diagonal (down-left). When a valid line is drawn from a starting cell, contiguous blocks of the same color along that direction are eliminated (i.e. counted) provided that the starting cell is not 0. The goal is to find the maximum number of contiguous blocks that can be eliminated in one move.

Formally, if you start from cell \( (i,j) \) (with \( grid[i][j] \neq 0 \)) and move in one of the allowed directions (given by the vector \( (d_i, d_j) \)), count the maximum number \( k \) such that for all \( t \) from 0 to \( k-1 \), we have \( grid[i+t\cdot d_i][j+t\cdot d_j] = grid[i][j] \). Your answer is the maximum such \( k \) over all starting cells and allowed directions.

inputFormat

The first line of the input contains two integers \( n \) and \( m \) (\( 1 \leq n,m \leq 1000 \)) representing the number of rows and columns in the grid respectively.

The following \( n \) lines each contain \( m \) space-separated integers denoting the grid. Each integer is either 0 (representing an empty cell) or a positive integer (representing a colored block).

outputFormat

Output a single integer, the maximum number of contiguous blocks of the same non-zero color that can be eliminated by drawing one valid line in any of the allowed directions.

4 5
1 2 2 3 4
2 2 0 2 2
1 0 0 0 2
1 1 1 1 1

5