138. 消息传输
内存限制:256 MB
时间限制:1.000 S
题目描述
在给定的 m x n (1 <= m, n <= 1000) 网格地图 grid 中,分布着一些信号塔,用于区域间通信。
每个单元格可以有以下三种状态:
值 0 代表空地,无法传递信号;
值 1 代表信号塔 A,在收到消息后,信号塔 A 可以在 1ms 后将信号发送给上下左右四个方向的信号塔;
值 2 代表信号塔 B,在收到消息后,信号塔 B 可以在 2ms 后将信号发送给上下左右四个方向的信号塔。
给定一个坐标 (j, k),输入保证坐标 (j, k) 位置一定有信号塔。在坐标 (j, k) 位置的信号塔触发一个信号。
要求返回网格地图中所有信号塔收到信号的最短时间,单位为 ms。如果有信号塔无法收到信号,则返回 -1。
输入
第一行:网格的列数 n。
第二行:网格的行数 m。
第三行:触发信号的信号塔坐标 (j, k)。
接下来的 m 行:每行包含 n 个整数,表示该行网格中每个位置的信号塔安装信息(通过空格间隔每个状态值)。
输出
输出返回 网格地图中所有信号塔收到信号的最小时间,单位为ms。如果不可能,返回-1。
样例输入 复制
3
3
1 0
0 1 2
1 2 1
0 1 2
样例输出 复制
4