P2658 Car Rally

Bo'ai City is going to hold a car rally. The course is uneven, so it is represented by an $M \times N$ grid of elevations $(1 \leq M, N \leq 500)$. The elevation of each cell is between $0$ and $10^9$. Some cells are designated as checkpoints. The organizers want to assign a difficulty coefficient $D$ to the entire course such that, for any two checkpoints, there exists a path between them where the elevation difference between any pair of adjacent cells on that path does not exceed $D$. In other words, $D$ is the minimum value that ensures all checkpoints are mutually reachable. Each cell is adjacent to the four cells to its north, south, east, and west.

The first line contains two integers $M$ and $N$. Lines $2$ through $M+1$: each line contains $N$ integers giving the elevations. Lines $M+2$ through $2M+1$: each line contains $N$ integers, each either $0$ or $1$; $1$ indicates that the cell is a checkpoint.

Output a single integer, the difficulty coefficient $D$.

Translated by ChatGPT 5