题意：给定一个(n*m)的地图，每个格子有初始高度。只能向右或向下移动，且要求第(i+1)步的高度必须比第(i)步恰好高(1)。每次操作可以使得任意一个格子的高度减(1)。问最少需要几次操作，使得地图中存在由((1,1))到((n,m))的路径。
思路：
DP。
由贪心原理可以知道，满足题意的路径中一定经过一个不需要降低高度的格子。以这个格子的高度为基准，计算可能经过的格子的花销，更新dp数组。
令(dp[i][j])表示从((1,1))到((i,j))所需要的最小操作数
转移方程：
(dp[i][j]=min(dp[i-1][j]+cost,dp[i][j-1]+cost))
而这个花销可以这样计算：
因为只能向右或向下移动，说明相邻两步移动的坐标差恰为1，又高度差也恰为1，所以：设这个基准高度为(H(x,y))，由题可知(H(x,y))与任意格子的应有高度(H(i,j))存在以下关系：
(H(i,j)=H(x,y)-(x-i+y-j))
所以做法是先通过遍历选定基准格子((x,y))，再计算得出可能路径上的格子的应有高度，据此再计算花销。
也可以通过(H(x,y))计算(H(1,1))，再以(H(1,1))计算各格子的应有高度，此时式子可简化为:
(H(i,j)=H(1,1)+i+j-2)
代码采用第二种方法。
typedef long long LL;
const LL INF = 1e18;
const int maxn = 100 + 10;
LL Map[maxn][maxn], dp[maxn][maxn];
int n, m;
LL solve(LL begin) {
//对于每一个不同的起点值，都要初始化dp数组
//注意从0开始初始化，否则更新dp[2][1]与dp[1][2]时会出错
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= m; j++) {
dp[i][j] = INF;
}
}
dp[1][1] = Map[1][1] - begin;
//起点格子的花销
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (i == 1 && j == 1) continue;
//dp[1][1]算过了，跳过
LL nowh = begin + i + j - 2;
//以标准高度为基准计算(i,j)格的应有高度
if (Map[i][j] < nowh) continue;
//实际高度比应有高度还小，没救了
LL cost = Map[i][j] - nowh;
//计算(i,j)格的花费
dp[i][j] = min(dp[i - 1][j] + cost, dp[i][j - 1] + cost);
}
}
return dp[n][m];
}
int main()
{
int t; cin >> t; while (t--) {
LL ans = INF;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> Map[i][j];
}
}
//尝试通过遍历所有可能的标准高度后计算得出起点值，再从这个起点值开始dp到终点
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
LL begin = Map[i][j] - i - j + 2;
if(begin<=Map[1][1]) ans = min(ans, solve(begin));
//否则实际起点值比理论起点值还小，这个起点值是不可用的
}
}
cout << ans << endl;
}
return 0;
}