生活随笔
收集整理的這篇文章主要介紹了
675. Cut Off Trees for Golf Event
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
這道題目最大的難點是理解題意。
文章目錄
題目理解
輸入：一個非負的二維數組
輸出：一個最短距離
規則：數組中的元素如果是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(List
<List
<Integer>> forest
) {List
<int[]> trees
= new ArrayList<int[]>();m
= forest
.size();n
= forest
.get(0).size();for(int i
=0;i
<m
;i
++){for(int j
=0;j
<n
;j
++){if(forest
.get(i
).get(j
)>1){trees
.add(new int[]{i
,j
,forest
.get(i
).get(j
)});}}}Collections
.sort(trees
, new Comparator<int[]>() {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(d
<0) return -1;ans
+= d
;sr
= tree
[0];sc
= tree
[1];}return ans
;}private int bfs(List
<List
<Integer>> forest
,int sr
,int sc
,int tr
,int tc
){Queue
<int[]> queue
= new ArrayDeque<int[]>();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 k
=0;k
<size
;k
++){int[] array
= queue
.poll();sr
= array
[0];sc
= array
[1];if(sr
== tr
&& sc
== tc
) return step
;for(int i
=0;i
<4;i
++){int nr
= sr
+ pos
[i
][0];int nc
= sc
+ pos
[i
][1]; if(nr
>=0 && nr
<m
&& nc
>=0 && nc
<n
&& 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)的節點就不能走。
總結
以上是生活随笔為你收集整理的675. Cut Off Trees for Golf Event的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
