P16119 [USTCPC 2026] Gradient Descent

"Phew, I finally figured out the formula for the discrete gradient!" Kruskal-chan stretched lazily, and her notebook in front of her was covered with grids. A classmate sitting next to her leaned over. "Are you still working on that gradient descent problem, Kruskal-chan?" "Yes! I'm thinking about how to make the algorithm run faster while still guaranteeing that it finds the minimum." Kruskal-chan tilted her head, looking puzzled. "Ah, so you want the maximum learning rate? But you also have to consider boundary cases." the classmate replied casually. Kruskal-chan's eyes lit up. "Right! Let's calculate it!"

For a grid scalar field $f$, define the discrete gradient at $(i, j)$ as follows: $$\begin{cases} \frac{\Delta f}{\Delta x}=\frac{f_{i+1,j}-f_{i-1,j}}{2}\\ \frac{\Delta f}{\Delta y}=\frac{f_{i,j+1}-f_{i,j-1}}{2} \end{cases}$$ If $(i, j)$ lies on the boundary of the grid, compute the corresponding one-sided difference only, and there is no need to divide by $2$. For example, for a point with $i=1$: $\frac{\Delta f}{\Delta x}=f_{i+1,j}-f_{i,j}$. Use the following gradient descent algorithm to find the minimum value in the grid: $$ \begin{cases} i\leftarrow i-\eta\cdot\frac{\Delta f}{\Delta x}\\ j\leftarrow j-\eta\cdot\frac{\Delta f}{\Delta y} \end{cases} $$ Here, $\eta$ is called the learning rate. To ensure that the step size is always an integer, $\eta$ must be even. If, during gradient descent, the coordinates go out of the grid range, the process ends immediately. Given an $n\times m$ grid scalar field and a starting coordinate (the starting coordinate is guaranteed not to be the global minimum), what is the maximum learning rate that can be used while still guaranteeing that the global minimum can be found? As long as the gradient descent process passes through a position that attains the global minimum value, it is considered to have found the global minimum.

The first line contains an integer $T$ ($1\le T\le 25000$), the number of test cases. For each test case, the first line contains four integers: the number of rows $n$ ($n\ge 2$), the number of columns $m$ ($m\ge 2$), the starting row $r$ ($1\le r\le n$), and the starting column $c$ ($1\le c\le m$). It is guaranteed that $nm\le 10^5$. Then follow $n$ lines, each containing $m$ integers. The $j$-th number in the $i$-th line denotes $f_{i,j}$ ($\lvert f_{i,j}\rvert\le 100$). It is guaranteed that $f_{r,c}\neq\min f$. It is guaranteed that $\sum nm\le 10^5$.

Output $T$ lines, one for each test case, giving the answer. If it is impossible to find the global minimum no matter what the learning rate is, output `Impossible`. Otherwise, output the maximum learning rate that can find the global minimum. Note: In this problem, the learning rate must be a positive even integer.

For the first sample, since the gradient at the starting position is $0$, the coordinates will never change, so it is impossible to reach a position that attains the global minimum. For the second sample, when $\eta=4$, the coordinates change as: $(1,3)\to(5,1)\to(5,5)$. At this point, the global minimum value $1$ is reached, so $\eta=4$ works. Any learning rate greater than $4$ will cause the first gradient descent step to go out of the grid range, so the answer is $4$. Translated by ChatGPT 5