|
| 1 | +//dijkstra |
| 2 | +classSolution { |
| 3 | +funminimumEffortPath(h:Array<IntArray>):Int { |
| 4 | +val minHeap=PriorityQueue<IntArray> { a, b-> a[2]- b[2] } |
| 5 | +val dirs= intArrayOf(0,1,0,-1,0) |
| 6 | +val n= h.size |
| 7 | +val m= h[0].size |
| 8 | +val visited=Array (n) {BooleanArray (m) } |
| 9 | + |
| 10 | +funisValid(x:Int,y:Int)= xin (0 until n)&& yin (0 until m) |
| 11 | + |
| 12 | + minHeap.add(intArrayOf(0,0,0)) |
| 13 | +while (minHeap.isNotEmpty()) { |
| 14 | +val (i, j, e)= minHeap.poll() |
| 15 | + |
| 16 | +if (i== n-1&& j== m-1)return e |
| 17 | + visited[i][j]=true |
| 18 | + |
| 19 | +for (kin0..3) { |
| 20 | +val i2= i+ dirs[k] |
| 21 | +val j2= j+ dirs[k+1] |
| 22 | +if (isValid(i2, j2)&&!visited[i2][j2]) { |
| 23 | +val e2=Math.abs(h[i][j]- h[i2][j2]) |
| 24 | + minHeap.add(intArrayOf(i2, j2, maxOf(e, e2))) |
| 25 | + } |
| 26 | + } |
| 27 | + } |
| 28 | + |
| 29 | +return0 |
| 30 | + } |
| 31 | +} |
| 32 | + |
| 33 | +// binary search + dfs to find min effort to reach end from start |
| 34 | +classSolution { |
| 35 | +funminimumEffortPath(h:Array<IntArray>):Int { |
| 36 | +val dirs= intArrayOf(0,1,0,-1,0) |
| 37 | +val n= h.size |
| 38 | +val m= h[0].size |
| 39 | +var visited=Array (n) {BooleanArray (m) } |
| 40 | + |
| 41 | +funisValid(x:Int,y:Int)= xin (0 until n)&& yin (0 until m) |
| 42 | + |
| 43 | +fundfs(x:Int,y:Int,k:Int):Boolean { |
| 44 | +if (x== n-1&& y== m-1)returntrue |
| 45 | + |
| 46 | + visited[x][y]=true |
| 47 | + |
| 48 | +for (iin0..3) { |
| 49 | +val x2= x+ dirs[i] |
| 50 | +val y2= y+ dirs[i+1] |
| 51 | +if (isValid(x2, y2)&&!visited[x2][y2]&&Math.abs(h[x][y]- h[x2][y2])<= k) { |
| 52 | +if (dfs(x2, y2, k)) |
| 53 | +returntrue |
| 54 | + } |
| 55 | + } |
| 56 | + |
| 57 | +returnfalse |
| 58 | + } |
| 59 | + |
| 60 | +var left=0 |
| 61 | +var right=1000000 |
| 62 | +var res= right |
| 63 | +while (left<= right) { |
| 64 | +val mid= (right+ left)/2 |
| 65 | + visited=Array (n) {BooleanArray (m) } |
| 66 | +if (dfs(0,0, mid)) { |
| 67 | + res= mid |
| 68 | + right= mid-1 |
| 69 | + }else { |
| 70 | + left= mid+1 |
| 71 | + } |
| 72 | + } |
| 73 | + |
| 74 | +return res |
| 75 | + } |
| 76 | +} |
| 77 | + |
| 78 | +//MST with kruskals algorith (using DSU) |
| 79 | +classSolution { |
| 80 | +funminimumEffortPath(h:Array<IntArray>):Int { |
| 81 | +val n= h.size |
| 82 | +val m= h[0].size |
| 83 | +val dsu=DSU(n* m) |
| 84 | +val edges= mutableListOf<IntArray>() |
| 85 | + |
| 86 | +func(x:Int,y:Int)= x* m+ y |
| 87 | + |
| 88 | +for (iin0 until n) { |
| 89 | +for (jin0 until m) { |
| 90 | +if (i+1< n) { |
| 91 | +val e=Math.abs(h[i][j]- h[i+1][j]) |
| 92 | + edges.add(intArrayOf(c(i, j), c(i+1, j), e)) |
| 93 | + } |
| 94 | +if (j+1< m) { |
| 95 | +val e=Math.abs(h[i][j]- h[i][j+1]) |
| 96 | + edges.add(intArrayOf(c(i, j), c(i, j+1), e)) |
| 97 | + } |
| 98 | + } |
| 99 | + } |
| 100 | + |
| 101 | + edges.sortWith { a, b-> a[2]- b[2] } |
| 102 | + |
| 103 | +for ((u, v, e)in edges) { |
| 104 | +if (dsu.union(u, v)) { |
| 105 | +if (dsu.find(c(0,0))== dsu.find(c(n-1, m-1))) { |
| 106 | +return e |
| 107 | + } |
| 108 | + } |
| 109 | + } |
| 110 | + |
| 111 | +return0 |
| 112 | + } |
| 113 | +} |
| 114 | + |
| 115 | +classDSU(valn:Int) { |
| 116 | +val parent=IntArray (n) { it } |
| 117 | +val size=IntArray (n) {1 } |
| 118 | + |
| 119 | +funfind(x:Int):Int { |
| 120 | +if (parent[x]!= x) |
| 121 | + parent[x]= find(parent[x]) |
| 122 | +return parent[x] |
| 123 | + } |
| 124 | + |
| 125 | +fununion(x:Int,y:Int):Boolean { |
| 126 | +val p1= find(x) |
| 127 | +val p2= find(y) |
| 128 | + |
| 129 | +if (p1== p2)returnfalse |
| 130 | + |
| 131 | +if (size[p1]> size[p2]) { |
| 132 | + parent[p2]= p1 |
| 133 | + size[p1]+= size[p2] |
| 134 | + }else { |
| 135 | + parent[p1]= p2 |
| 136 | + size[p2]+= size[p1] |
| 137 | + } |
| 138 | + |
| 139 | +returntrue |
| 140 | + } |
| 141 | +} |