2023 蓝桥杯热身赛

Problem P29. 旱地行舟(二)

SLF 觉得之前用的地图还是太粗糙了,不能表现出最短路的详细路径。为了让陆地上拖船的脚夫更轻松一点,SLF 让 YDX 画了一张更简单、更详细的地图。这份地图更大,但只由 01 组成,代表经过该地所耗费的路程。在地图上只能上、下、左、右走,不能走出边界。设地图左上角为起点,右下角为终点。求从起点到终点经过的最短路程。

输入

先输入一个整数 T \ (1 \leq T \leq 10),代表测试样例的个数。

对于每个测试样例,输入一个正整数 N \ (2 \leq N \leq 500)。接下来给出 N 行,每行 N 个以空格间隔的数字来代表格子。这些数字只由 01 组成。

输出

对于每个测试样例,每行输出一个数,代表从起点到终点的最小路程(计算路程时计算上起点和终点上的数字)。

样例

标准输入 复制文本
2
2
1 0
1 1
3
1 0 1
1 1 1
1 0 1
标准输出 复制文本
2
3

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 18
通过 3