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