在小美和小团生活的城市中，有n行m列共计n*m个十字路口，第i行j列的十字路口有两个属性a_ij，b_ij。当行人处在i行j列的路口，对于任意非负整数k: 当时间处在[k*a_ij+k*b_ij), (k+1)*a_ij+k*b_ij)时，行人可以选择走到i±1行j列的路口。 当时间处在[(k+1)*a_ij+k*b_ij), (k+1)*a_ij+(k+1)*b_ij)时，行人可以选择走到i行j±1列的路口。 每次移动花费的时间为1，且要保证将要去的十字路口存在，即属于n*m个路口当中。可以选择原地静止不动。 在第0时刻，小美处在x_s行y_s列的十字路口处，要去x_t行y_t列的十字路口找小团。小团原地不动等小美，请问小美所花费的时间最少是多少?
第一行六个正整数n，m，x_s，y_s，x_t，y_t，含义如上文所示。以样例第一行【5、5、2、4、4、3】 共计6个数字为例，前两位数字代表有5*5的二维数组，三、四位数字代表小美处在2行4列的十字路口处，五、六位数字代表要去4行3列的十字路口找小团。 接下来n行每行m个正整数，在样例中为第一个5*5的二维数组，第i行第j个数代表i行j列十字路口的属性a_ij。 接下来n行每行m个正整数，在样例中为第二个5*5的二维数组，第i行第j个数代表i行j列十字路口的属性b_ij。 对于100%的数据，1≤n，m，x_s，y_s，x_t，y_t，a_ij，b_ij≤100。
输出1行1个整数代表答案。
5 5 2 4 4 3 2 1 1 3 1 1 4 2 3 1 4 4 4 2 1 3 1 1 2 4 5 1 5 5 1 5 3 4 1 3 1 1 2 2 2 2 1 4 4 5 1 1 5 3 3 3 2 1 3 3
3
考点：广度优先搜索(BFS)
限制 1 秒 / 256MB ｜ 标准输入输出
推荐方向：广度优先搜索(BFS)
本题切入点
时间会改变每个路口可走的方向，把「路口 + 到达时刻」作为状态做 BFS/最短路，注意等待时间的计算。
按层扩散搜索，无权图上第一次到达即最短路。
思路框架（广度优先搜索(BFS) 通法 · 非本题专属）
实现要点：标记访问必须在入队时做，不能在出队时做，否则会重复入队甚至超时。
复杂度：时间 O(V+E) ｜ 空间 O(V)
该范式的通法易错点
对照本题
样例 1
5 5 2 4 4 3 / 2 1 1 3 1 / 1 4 2 3 1 / 4 4 4 2 1 / 3 1 1 2 4 / 5 1 5 5 1 / 5 3 4 1 3 / 1 1 2 2 2 / 2 1 4 4 5 / 1 1 5 3 3 / 3 2 1 3 33解析由校招宝本地引擎整理（依据源站考点标签 / 人工判题标注 / 题面规模信号），非官方题解，仅供思路参考。
本题来源：美团2023校招技术第8场编程题。