站内搜索本网站怎么做,扬州市规划建设局网站,中铁建设集团有限公司招聘官网,福州晋安区建设局网站这道题目最大的难点是理解题意。 文章目录题目理解题目理解
输入#xff1a;一个非负的二维数组 输出#xff1a;一个最短距离 规则#xff1a;数组中的元素如果是0#xff0c;表示障碍#xff0c;不能通过。如果是1#xff0c;表示可以行走的地面。如果大于1表示树的高…这道题目最大的难点是理解题意。
文章目录题目理解题目理解
输入一个非负的二维数组 输出一个最短距离 规则数组中的元素如果是0表示障碍不能通过。如果是1表示可以行走的地面。如果大于1表示树的高度需要被砍了以后才能行走。 现在要求每次都从(0,0)出发按照树的高度从低到高砍树。把所有树都砍完的最短距离是多少。如果不能砍完所有的树则返回-1。
[ [1,2,3], [0,0,4], [7,6,5] ] 以上面的数组为例。先对所有非0节点按照数值排序。这个例子中砍树的顺序应该是(0,0)-(0,1)-(0,2)-(1,2)-(2,2)-(2,1)-(2,0)。 那么先计算(0,0)到(0,0)的最短距离d1。 接着计算(0,0)到(0,1)的最短距离d2。 接着计算(0,1)到(0,2)的最短距离d3. … 所有距离相加就是最短距离。
计算两个点之间的最短距离可以使用bfs。官方解答中还有a星算法。没想明白为什么那么做。 时间复杂度O((mnmn))。我们可能要计算mn个节点的最短路径每个节点计算过程中又可能与m*n个节点有关系。
class Solution {private int[][] pos new int[][]{{-1,0},{1,0},{0,-1},{0,1}};private int m;private int n;public int cutOffTree(ListListInteger forest) {Listint[] trees new ArrayListint[]();m forest.size();n forest.get(0).size();for(int i0;im;i){for(int j0;jn;j){if(forest.get(i).get(j)1){trees.add(new int[]{i,j,forest.get(i).get(j)});}}}Collections.sort(trees, new Comparatorint[]() {public int compare(int[] o1, int[] o2) {return o1[2] - o2[2];}});int ans 0, sr 0,sc 0;for(int[] tree : trees){int d bfs(forest,sr,sc,tree[0],tree[1]);if(d0) return -1;ans d;sr tree[0];sc tree[1];}return ans;}private int bfs(ListListInteger forest,int sr,int sc,int tr,int tc){Queueint[] queue new ArrayDequeint[]();queue.offer(new int[]{sr,sc});boolean[][] seen new boolean[m][n];seen[sr][sc] true;int step 0;while(!queue.isEmpty()){int size queue.size();for(int k0;ksize;k){int[] array queue.poll();sr array[0];sc array[1];if(sr tr sc tc) return step;for(int i0;i4;i){int nr sr pos[i][0];int nc sc pos[i][1]; if(nr0 nrm nc0 ncn seen[nr][nc]false forest.get(nr).get(nc)0){queue.offer(new int[]{nr,nc});seen[nr][nc]true;}}}step;}return -1;}
}总结我第一个没有想到的地方是可以先对树的高度排序。第二个没有想到的是按照从低到高走找到每一步的最短路径和就是总体最短路径。第三个没有想到的是在bfs过程中我想判断条件forest.get(nr).get(nc)应该大于forest.get(sr).get(sc),这是因为我审题不清楚造成的误解。题目要求按照从低到高砍树在从(sr,sc)到(tr,tc)过程中只要节点值不为0 都可以通过并不是说值(sr,sc)的节点就不能走。
