675. Cut Off Trees for Golf Event

675. Cut Off Trees for Golf Event

You are asked to cut off trees in a forest for a golf event. The forest is represented as a non-negative 2D map, in this map:

0 represents the obstacle can’t be reached. 1 represents the ground can be walked through. The place with number bigger than 1 represents a tree can be walked through, and this positive number represents the tree’s height. You are asked to cut off all the trees in this forest in the order of tree’s height - always cut off the tree with lowest height first. And after cutting, the original place has the tree will become a grass (value 1).

You will start from the point (0, 0) and you should output the minimum steps you need to walk to cut off all the trees. If you can’t cut off all the trees, output -1 in that situation.

You are guaranteed that no two trees have the same height and there is at least one tree needs to be cut off.

Example 1:

Input: [ [1,2,3], [0,0,4], [7,6,5]]Output: 6

Example 2:

Input: [ [1,2,3], [0,0,0], [7,6,5]]Output: -1

Example 3:

Input: [ [2,3,4], [0,0,5], [8,7,6]]Output: 6

Explanation: You started from the point (0,0) and you can cut off the tree in (0,0) directly without walking. Hint: size of the given matrix will not exceed 50x50.

思路： 题目是求 从(0,0)点出发用最短的路径走到树高最低的点，然后再从当前最高最低的点以最短路径走到树高第二低的点，依次类推直到走完所有点，最后累加这些最短距离。 1、先将矩阵里大于0的点进行排序（排序时要记录对应的坐标） 2、以广度优先的策略找到给定的出发点到其它所有点的最短单元距离 3、以(0,0)为初始的出发点，再遍历树高的有序集拿出当前最小的树高，出每一次到达最小树高的最短路径 4、累加这些最短距离，若有不可达点则返回-1

class Solution { int[][] direct = {{1, 0},{-1, 0},{0, -1},{0, 1}};//四个方向 int[][] dist; public int cutOffTree(List> forest) { int result = 0; int rows = forest.size(); int cols = forest.get(0).size(); int[][] matrix = new int[rows][cols]; //TreeMap有自动键值排序的功能，用其存储<树高，与树所在矩阵的坐标> TreeMap map = new TreeMap (); dist = new int[rows][cols]; for(int i=0;i keys = map.keySet(); //初始坐标 int[] start = {0, 0}; for(int key : keys){ if(key > 0){ int[] end = map.get(key); //拿到当前最小高度的树的坐标 minDist(start,matrix); //求出出发点到其它所有点的最短距离 int d = dist[end[0]][end[1]]; //拿到出发点到当前最小树高的距离 if(d == Integer.MAX_VALUE) //若无法到达则返回-1 return -1; result += d; //进行累加 start = end; //将当前最小高度的树作为下一轮的出发点 } } return result; } //求出给定的点到其它点之间的最短距离。 void minDist(int[] start,int[][] matrix){ int rows = matrix.length; int cols = matrix[0].length; //初始化dist数组，默认为MAX for(int i=0;i q = new LinkedList(); q.add(start); //出发点入队 dist[start[0]][start[1]] = 0; //到自己的距离为0 while(!q.isEmpty()){ int[] p = q.poll(); //可选的四个方向 for(int[] dir : direct ){ int x = p[0]; int y = p[1]; int nx = x + dir[0]; int ny = y + dir[1]; int[] np = {nx,ny}; //可入队的点要满足：1.格式 2.不是障碍物 3.出发点到它的距离小于其本身在dist数组里的距离 if(nx=0 && ny=0 && matrix[nx][ny]!=0 && dist[nx][ny] > dist[x][y]+1){ q.add(np); dist[nx][ny] = dist[x][y] + 1; } } } }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。