‹ 上一题下一题 ›

j01467. 带起火时间的逃生未做

1000 ms 256 MB 测试点 10 J-31·图论遍历与泛洪 J·算法自拟题图的深度优先遍历图的广度优先遍历深度优先搜索广度优先搜索

文件读写输入j01467.in输出j01467.out

题目描述

矩阵每格整数 $t_{i}$ ：起火时刻（ $1 0^{9}$ 表示永不燃； $- 1$ 表示墙不可进入）。人从 $S$ （第 0 分钟在 $S$ ）每分钟走一格，进入一格当且仅当 $t_{i} >$ 到达时刻（ $S$ 保证安全）。求到 $E$ 最少分钟；不可达 -1。

输入格式

第一行 $n, m$ ；矩阵；最后一行 $S_{r} S_{c} E_{r} E_{c}$ 。

输出格式

一个整数。

样例

输入

1 3
9 2 9
1 1 1 3

输出

数据范围

$1 \leq n, m \leq 1000$
$- 1 \leq t_{i} \leq 1 0^{9}$
$1 \leq S_{r}, E_{r} \leq n$ ， $1 \leq S_{c}, E_{c} \leq m$

输入

输出

答案