Version #1 BFS
题目是非常straightforward的，主要hard在写起来非常麻烦
我一开始在visit上用 (y << 6) | x对坐标进行hash，避免了visited[rows][cols]但是结果非常的慢，慢出了0%。。。
写了一个bug就是没有考虑start 和end重合的edge case，这种情况如果不特殊考虑的话会return 2 步， 但是实际上需要return 0 部
P.S.这里没有用到从hash = (y << 6) | x里面取x, y的use case， 但是想了一下如果要做的话应该是
mask = (1 << 6) - 1 得到 1000000 - 1 = 111111
x = hash & mask
y = hash >> 6
40.72 %
Without using lambda
25.18 %
class Solution {
private int rows;
private int cols;
public int cutOffTree(List<List<Integer>> forest) {
this.rows = forest.size();
this.cols = forest.get(0).size();
// curr[0] height, curr[1] x, curr[2] y
List<int[]> trees = new ArrayList<>();
for (int y = 0; y < rows; y++) {
for (int x = 0; x < cols; x++) {
if (forest.get(y).get(x) > 1) {
trees.add(new int[]{forest.get(y).get(x), x, y});
}
}
}
Collections.sort(trees, Comparator.comparing((int[] arr) -> arr[0]));
int result = 0;
int[] start = new int[]{0, 0};
for (int[] end : trees) {
int step = getDist(start, end, forest);
// System.out.println(start[1] + " " + start[2] + " " + end[1] + " " + end[2] + " -> " + step);
if (step == -1) {
return -1;
}
result += step;
start[0] = end[1];
start[1] = end[2];
}
return result;
}
private int[] dx = new int[]{1, 0, -1, 0};
private int[] dy = new int[]{0, -1, 0, 1};
// private int mask = (1 << 6) - 1;
private int getDist(int[] start, int[] end, List<List<Integer>> forest) {
boolean[][] visited = new boolean[rows][cols];
if (start[0] == end[1] && start[1] == end[2]) return 0;
Queue<int[]> que = new LinkedList<>();
que.offer(start);
// Set<Integer> visited = new HashSet<>();
int level = 0;
while(!que.isEmpty()) {
level++;
int size = que.size();
while (size-- > 0) {
int[] curr = que.poll();
for (int i = 0; i < 4; i++) {
int nextX = curr[0] + dx[i];
int nextY = curr[1] + dy[i];
if (nextX == end[1] && nextY == end[2]) return level;
if (nextX >= 0 && nextX < cols && nextY >= 0 && nextY < rows
&& forest.get(nextY).get(nextX) > 0 && !visited[nextY][nextX]) {
que.offer(new int[]{nextX, nextY});
visited[nextY][nextX] = true;
}
}
}
}
return -1;
}
}
