在小美和小团生活的城市中，有n 行m 列共计n*m 个十字路口，第i 行j 列的十字路口有两个属性aij ，b­ij 。当行人处在i 行j 列的路口，对于任意非负整数k: 当时间处在[k*aij+k*b­ij), (k+1)*aij+k*bij) 时，行人可以选择走到i ±1 行j 列的路口。 当时间处在[(k+1)*aij+k*bij), (k+1)*aij+(k+1)*b­ij) 时，行人可以选择走到i 行j ±1 列的路口。 每次移动花费的时间为1 ，且要保证将要去的十字路口存在，即属于n*m 个路口当中。可以选择原地静止不动。 在第0 时刻，小美处在xs 行ys 列的十字路口处，要去xt 行yt 列的十字路口找小团。小团原地不动等小美，请问小美所花费的时间最少是多少 ?-笔试面试资料

使用BFS进行求解，每个时刻都对可能移动的方向进行尝试，将下一个时刻可能到达的位置放入到一个队列中。但是在移动的过程中需要注意：由于移动收到所处时间段的限制，有可能为了花费更少的时间，本时刻决定不移动，等到下一时刻往更高效的方向进行移动。在这种情况下，下一个时刻仍然在现在的位置。而时间对于移动操作的约数，可以这么来表征：

(1) 对于区间[k*a_ij+k*b­_ij), (k+1)*a_ij+k*b_ij)，左端点是a_ij+b_ij的正数倍，右端点是一个开区间，比左端点多了不到aij，因此当时刻除以a_ij+b_ij的余数小于a_ij时，所处的时刻应该满足这个约束。

(2) 对于区间[(k+1)*a_ij+k*b_ij), (k+1)*a_ij+(k+1)*b­_ij)，紧邻(1)中区间的右侧，所以a_ij<=余数<a_ij+b_ij时就是这种情况。

import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.Queue; import java.util.LinkedList;  class Node {     public int x;     public int y;     public Node(int x, int y) {         this.x = x;         this.y = y;     } }  public class Main {     static int n, m, xs, ys, xt, yt;     static int[][] a, b;             // 十字路口的属性     static boolean[][] visited;      // 节点是否已经被走过     static int[] direction = new int[]{0, -1, 1};   // 移动方向     public static void main(String[] args) throws IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         String[] params = br.readLine().trim().split(" ");         n = Integer.parseInt(params[0]);         m = Integer.parseInt(params[1]);         xs = Integer.parseInt(params[2]);         ys = Integer.parseInt(params[3]);         xt = Integer.parseInt(params[4]);         yt = Integer.parseInt(params[5]);         a = new int[n + 1][m + 1];         b = new int[n + 1][m + 1];         visited = new boolean[n + 1][m + 1];         for(int i = 1; i <= n; i++){             params = br.readLine().trim().split(" ");             for(int j = 1; j <= m; j++)                 a[i][j] = Integer.parseInt(params[j - 1]);         }         for(int i = 1; i <= n; i++){             params = br.readLine().trim().split(" ");             for(int j = 1; j <= m; j++)                 b[i][j] = Integer.parseInt(params[j - 1]);         }         int cost = 0;   // 初始化花费的时间         visited[xs][ys] = true;         System.out.println(bfs(cost));     }          private static int bfs(int cost) {         // 用于存储同一时间点可能到达的节点         Queue<Node> queue = new LinkedList<>();         // 先把起点加入队列         queue.offer(new Node(xs, ys));         while(!queue.isEmpty()){             int len = queue.size();   // 当前时刻有len个可能的位置             while(len-- > 0){                 Node cur = queue.poll();                 // 找到了小团，直接返回耗时                 if(cur.x == xt && cur.y == yt) return cost;                 // 在当前位置尝试移动                 for(int j = 0; j < direction.length; j++){                     int remainder = cost % (a[cur.x][cur.y] + b[cur.x][cur.y]);                     int x = cur.x, y = cur.y;                     if(remainder < a[x][y]){                         // 时间处于[k*aij+k*bij), (k+1)*aij+k*bij)                         x += direction[j];                     }else{                         // 时间处于[(k+1)*aij+k*bij), (k+1)*aij+(k+1)*bij)                         y += direction[j];                     }                     // 移动位置不合法                     if(x < 1 || x > n || y < 1 || y > m) continue;                     // 如果下一个位置还没有走过或者当前时刻不进行移动，就往队列中添加节点                     if(!visited[x][y] || j == 0){                         queue.offer(new Node(x, y));                         visited[x][y] = true;                     }                 }             }             cost ++;         }         return cost;     } }