在小美和小团生活的城市中,有n 行m 列共计n*m 个十字路口,第i 行j 列的十字路口有两个属性aij ,bij 。当行人处在i 行j 列的路口,对于任意非负整数k: 当时间处在[k*aij+k*bij), (k+1)*aij+k*bij) 时,行人可以选择走到i ±1 行j 列的路口。 当时间处在[(k+1)*aij+k*bij), (k+1)*aij+(k+1)*bij) 时,行人可以选择走到i 行j ±1 列的路口。 每次移动花费的时间为1 ,且要保证将要去的十字路口存在,即属于n*m 个路口当中。可以选择原地静止不动。 在第0 时刻,小美处在xs 行ys 列的十字路口处,要去xt 行yt 列的十字路口找小团。小团原地不动等小美,请问小美所花费的时间最少是多少 ?-笔试面试资料
这是qklbishe.com第7297 篇笔试面试资料
提供答案分析,通过本文《在小美和小团生活的城市中,有n 行m 列共计n*m 个十字路口,第i 行j 列的十字路口有两个属性aij ,bij 。当行人处在i 行j 列的路口,对于任意非负整数k: 当时间处在[k*aij+k*bij), (k+1)*aij+k*bij) 时,行人可以选择走到i ±1 行j 列的路口。 当时间处在[(k+1)*aij+k*bij), (k+1)*aij+(k+1)*bij) 时,行人可以选择走到i 行j ±1 列的路口。 每次移动花费的时间为1 ,且要保证将要去的十字路口存在,即属于n*m 个路口当中。可以选择原地静止不动。 在第0 时刻,小美处在xs 行ys 列的十字路口处,要去xt 行yt 列的十字路口找小团。小团原地不动等小美,请问小美所花费的时间最少是多少 ?-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。
答案:
在小美和小团生活的城市中,有n行m列共计n*m个十字路口,第i行j列的十字路口有两个属性aij,bij。当行人处在i行j列的路口,对于任意非负整数k:
当时间处在[k*aij+k*bij), (k+1)*aij+k*bij)时,行人可以选择走到i±1行j列的路口。
当时间处在[(k+1)*aij+k*bij), (k+1)*aij+(k+1)*bij)时,行人可以选择走到i行j±1列的路口。
每次移动花费的时间为1,且要保证将要去的十字路口存在,即属于n*m个路口当中。可以选择原地静止不动。
在第0时刻,小美处在xs行ys列的十字路口处,要去xt行yt列的十字路口找小团。小团原地不动等小美,请问小美所花费的时间最少是多少?
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; } }
文章部分来自互联网,侵权联系删除
www.qklbishe.com
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » 在小美和小团生活的城市中,有n 行m 列共计n*m 个十字路口,第i 行j 列的十字路口有两个属性aij ,bij 。当行人处在i 行j 列的路口,对于任意非负整数k: 当时间处在[k*aij+k*bij), (k+1)*aij+k*bij) 时,行人可以选择走到i ±1 行j 列的路口。 当时间处在[(k+1)*aij+k*bij), (k+1)*aij+(k+1)*bij) 时,行人可以选择走到i 行j ±1 列的路口。 每次移动花费的时间为1 ,且要保证将要去的十字路口存在,即属于n*m 个路口当中。可以选择原地静止不动。 在第0 时刻,小美处在xs 行ys 列的十字路口处,要去xt 行yt 列的十字路口找小团。小团原地不动等小美,请问小美所花费的时间最少是多少 ?-笔试面试资料