logo AlgoBeat OnlineJudge
登录 注册

#216134. [USTCPC 2026] Gradient Descent

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

“呼~终于把离散梯度的公式搞懂了!”克露丝卡尔酱伸了个懒腰,面前的笔记本上画满了网格。

坐在旁边的同学探过头来:“克露丝卡尔酱还在研究那个梯度下降问题吗?”

“嗯嗯!我在想,怎么在保证找到最小值的前提下让算法跑得快一点呢?”克露丝卡尔酱歪着头,露出困惑的表情。

“啊,那不就是要求最大学习率吗?不过还要考虑边界情况呢。”同学随口说道。

克露丝卡尔酱眼睛一亮:“对呀!让我们来算算吧~”


对于网格标量场 ,按以下方式定义 处的离散梯度:

位于网格边界,则相应地只计算单侧差分,并且不需要除以 ,例如对于 的点:

使用如下的梯度下降算法寻找网格中的最小值:

其中 称为学习率,为了保证步长总为整数,需要保证 为偶数。若梯度下降过程中坐标超出了网格范围,则直接结束。

给定 尺寸的网格标量场以及初始坐标(保证初始坐标不是全局最小值),在能够找到全局最小值的前提下,学习率最大可以设置为多少?

只要在梯度下降过程中经过了取到全局最小值的位置,即视为找到了全局最小值。

输入格式

首先输入一行,包含一个整数 (),表示测试数据组数。

每组数据首先输入一行,包含四个整数,分别表示网格的行数 ()、列数 (),初始位置所在行 ()、所在列 ()。保证

接下来输入 行,每行 个整数,其中第 行的第 个数表示 ()。保证

保证

输出格式

输出 行,表示每组数据的答案。若无论学习率是多少,都无法找到全局最小值,输出 Impossible,否则输出能够找到全局最小值的最大的学习率。

注意:本题中的学习率必须为大于零的偶数。

样例

样例输入 1

2
2 3 1 3
1 2 2
1 1 2
5 5 1 3
1 2 3 3 2
2 3 2 3 3
3 1 1 2 2
2 3 2 1 3
2 1 1 3 1

样例输出 1

Impossible
4

数据范围与提示

对于第一组样例,由于初始位置的梯度为 ,因此坐标将永远不变,无法到达取到全局最小值的位置。

对于第二组样例,当 时,坐标变化的过程为: ,此时取到全局最小值 ,因此 满足条件。而任何大于 的学习率均会导致第一次梯度下降就超出网格范围,因此答案为