在小美和小团生活的城市中,有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 列的十字路口找小团。小团原地不动等小美,请问小美所花费的时间最少是多少 ?-笔试面试资料

这是qklbishe.com第7297 篇笔试面试资料
提供答案分析,通过本文《在小美和小团生活的城市中,有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 列的十字路口找小团。小团原地不动等小美,请问小美所花费的时间最少是多少 ?-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

在小美和小团生活的城市中,有nm列共计n*m个十字路口,第ij列的十字路口有两个属性aijij。当行人处在ij列的路口,对于任意非负整数k:

当时间处在[k*aij+k*b­ij), (k+1)*aij+k*bij)时,行人可以选择走到i±1j列的路口。

当时间处在[(k+1)*aij+k*bij), (k+1)*aij+(k+1)*b­ij)时,行人可以选择走到ij±1列的路口。

每次移动花费的时间为1,且要保证将要去的十字路口存在,即属于n*m个路口当中。可以选择原地静止不动。

在第0时刻,小美处在xsys列的十字路口处,要去xtyt列的十字路口找小团。小团原地不动等小美,请问小美所花费的时间最少是多少?

在小美和小团生活的城市中,有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*aij+k*b­ij), (k+1)*aij+k*bij),左端点是aij+bij的正数倍,右端点是一个开区间,比左端点多了不到aij,因此当时刻除以aij+bij的余数小于aij时,所处的时刻应该满足这个约束。
(2) 对于区间[(k+1)*aij+k*bij), (k+1)*aij+(k+1)*b­ij),紧邻(1)中区间的右侧,所以aij<=余数<aij+bij时就是这种情况。
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;     } }

2021-03-06 21:44:34 回复(1)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 在小美和小团生活的城市中,有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 列的十字路口找小团。小团原地不动等小美,请问小美所花费的时间最少是多少 ?-笔试面试资料

提供最优质的资源集合

立即查看 了解详情