解题思路

本题本质是一个网格图上的最短路问题。由于每个工作站都可以同时、无限量地派出工作人员，并且移动代价一致（上下左右、每步 1 分钟），因此从所有工作站同时出发，在可通行的格子（0、1、3）上进行多源 BFS（图论），即可一次性得到每个位置到最近工作站的最短时间。

• 将所有值为 3 的工作站位置同时入队，距离置为 0。

• 进行 BFS 扩展：只能走到非障碍（不为 2）且未访问过的位置，邻居距离为当前距离 + 1。

• BFS 完成后：

  • 在所有基站位置（值为 1）中，取其被访问到的距离的最大值，这就是完成所有可维护（可达）基站所需的最小时间（最后到达的那一个决定总耗时）。
  • 若不存在任何一个可达的基站（即所有 1 的位置都未被访问），按题意输出 -1。

题目内容

在大小为 $m*m$ 的城市中分布着一些基站，这些基站需要进行例行的维护工作。维护工作由多个工作站中的工作人员来完成。工作人员可以从工作站出发，只能上下左右移动，每走一次消耗时间 $1$ 分钟，忽略维护的手机开销（到达即完成维护）。

城市中有一些工作人员无法跨越的障碍，遇到阻碍需要绕过，假定每个工作站中工作人员数量不限。请输出最少需要多少时间，工作人员可以维护完所有的基站。请输出最少多少制间完成所有可维护基站的维护，如果出现所有基站都无法维护的情况，请返回 $-1$ 。不考虑整个城市中都没有基站的情况，用例保证一定有需要维护的基站。

地图中，$0$ 代表空地，可以穿过。$1$ 代表基站，也可以穿过。$2$ 代表障碍，无法穿过。$3$ 代表工作站。

输入描述

第一行给出一个正整数 $m(0<1000)$ 。第二行开始到第 $m+1$ 行，每一行 $m$ 个数字，代表地图中第 $1$ 到 第 $m$ 行的空地、基站、障碍、工作站等信息。

输出描述

请输出维护花费的最小时间

样例1

输入

3
3 2 3
2 1 2
1 0 0

输出

-1

说明

位置 $[0,0]$ 和 $[0,2]$ 的工作站都被障碍完全阻隔无法派出工作人员，所有基站都无法维护。

样例2

输入

3
3 1 0
1 3 0
1 0 1

输出

2

说明

工作站位置在地图的 $[0,0]$ 和 $[1,1]$ ，工作站同时派出工作人员维护的位置在 $[0,1]、[1,0]、[2,0]、[2,2]$ 位置的 $4$ 个基站，工作站 $[1,1]$ 的工作人员维护 $[2,2]$ 基站需要走 $2$ 步。

工作站 $[0,0]$ 的工作人员派出 $3$ 名工作人员，维护位置在 $[0,1]、[1,0]、[2,0]$ 的 $3$ 个基站，最多需要走 $2$ 步。维护所有基站花费的最小时间是 $2$ 分钟。