P14278 [ROI 2014 Day2] 健康饮食

**译自 [ROI 2014](https://neerc.ifmo.ru/school/archive/2013-2014.html) Day2 T3.** ***[Здоровое питание](https://neerc.ifmo.ru/school/archive/2013-2014/ru-olymp-roi-2014-statement-day2.pdf)***

某大学的学生城规划为一个 $n \times n$ 的正方形网格，每个格子里都有一栋建筑。如果两栋建筑位于有公共边的相邻格子中，它们之间就有一条连通的通道。在正方形的**左上角**是学生宿舍，在**右下角**是教学楼。每栋建筑中（包括宿舍与教学楼）都设有一台自动售货机，每台售货机只出售一种食品，例如：仅售咖啡，或仅售肉馅饼等。学生每天都会从宿舍出发，沿着通道前往教学楼，并选择一条**最短路径**。 校方希望研究学生在行进过程中购买食品的多样性。对于每一台售货机 $A_{i,j}$，希望找到一条**经过该售货机的最短路径**，并且该路径上与 $A_{i,j}$ 出售相同食品的售货机数量尽可能多。该数量称为售货机 $A_{i,j}$ 的**冗余度**。已知售货机 $A_{1,1}$ 位于宿舍内，而 $A_{n,n}$ 位于教学楼内。 请编写程序，根据各售货机所售食品的信息，统计冗余度为 $1, 2, \ldots, 2n - 1$ 的售货机各有多少台。

第一行包含一个整数 $n$（$2 \leqslant n \leqslant 1500$）。 接下来的 $n$ 行，每行包含 $n$ 个整数。第 $i$ 行第 $j$ 个数表示售货机 $A_{i,j}$ 所售食品的编号。食品编号的取值范围为 $1$ 到 $n^2$。

输出共 $(2n - 1)$ 个整数，第 $k$ 个数表示冗余度等于 $k$ 的售货机数量（$k = 1, 2, \ldots, 2n - 1$）。

本题共 50 个测试，每个测试独立计分，每个测试 2 分。测试中使用的 $n$ 值如下表所示： | 测试编号 | $n$ | 测试编号 | $n$ | 测试编号 | $n$ | 测试编号 | $n$ | 测试编号 | $n$ | |:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:| | 1 | 2 | 11 | 50 | 21 | 200 | 31 | 550 | 41 | 1050 | | 2 | 4 | 12 | 60 | 22 | 225 | 32 | 600 | 42 | 1100 | | 3 | 6 | 13 | 70 | 23 | 250 | 33 | 650 | 43 | 1150 | | 4 | 8 | 14 | 80 | 24 | 275 | 34 | 700 | 44 | 1200 | | 5 | 10 | 15 | 90 | 25 | 300 | 35 | 750 | 45 | 1250 | | 6 | 15 | 16 | 100 | 26 | 325 | 36 | 800 | 46 | 1300 | | 7 | 20 | 17 | 120 | 27 | 350 | 37 | 850 | 47 | 1350 | | 8 | 25 | 18 | 140 | 28 | 400 | 38 | 900 | 48 | 1400 | | 9 | 30 | 19 | 160 | 29 | 450 | 39 | 950 | 49 | 1450 | | 10 | 40 | 20 | 180 | 30 | 500 | 40 | 1000 | 50 | 1500 |