题目描述

给定一个 N行 M列的 01 矩阵 A，A[i][j] 与 A[k][l] 之间的曼哈顿距离定义为：dist(A[i][j],A[k][l])=|i−k|+|j−l|

随后求出一个 N行 M 列的整数矩阵 B，其中：B[i][j]=min(1≤x≤N,1≤y≤M,A[x][y]=1)dist(A[i][j],A[x][y])

最后在该矩阵上求从B[1][1]到B[N][M]（只能向右或者向下移动）路径的相加最大值Max。[拒绝决定不想讲故事 拒绝决定干净出题]

输入格式

输入第一行是数据个数 T 。(1 接下来的 T 组数据： 第一行包括矩阵A的行数 N 和列数 M 。(1 随后的 2 到 N+1 行 每行 M个数字 ( 0 或 1 )。

提示：这题不用循环读入

输出格式

一共 T 行 每行输出一个数字Max。

1
3 4
0 0 0 1
0 0 1 1
0 1 1 0

7

提示

测试样例中的矩阵B长这样↓ 3 2 1 0  2 1 0 0  1 0 0 1  MAX为7 其中最长的一条路径相加是 3(1,1)->2(1,2)->1(1,3)->0(1,4)->0(2,4)->1(3,4) 这条路径相加和为7.