675 Cut Off Trees for Golf Event
class Solution {
public int cutOffTree(List<List<Integer>> forest) {
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
return a[2] - b[2];
});
for (int i = 0; i < forest.size(); i++){
for (int j = 0; j < forest.get(i).size(); j++){
if (forest.get(i).get(j) > 1) pq.offer(new int[]{i, j, forest.get(i).get(j)});
}
}
//System.out.println("pq: " + pq.size());
int ans = 0;
int[] start = new int[2];
while (!pq.isEmpty()){
int[] target = pq.poll();
int step = bfs(forest, start, target);
if (step < 0) return -1;
ans += step;
start[0] = target[0];
start[1] = target[1];
}
return ans;
}
private int bfs(List<List<Integer>> forest, int[] start, int[] target){
int[] x_moves = {0, 1, 0, -1};
int[] y_moves = {1, 0, -1, 0};
Set<int[]> seen = new HashSet<>();
int n = forest.size(), m = forest.get(0).size();
boolean[][] visited = new boolean[n][m];
Queue<int[]> q = new LinkedList<>();
int step = 0;
q.offer(start);
//seen.add(start);
visited[start[0]][start[1]] = true;
while (!q.isEmpty()){
int size = q.size();
for (int i = 0; i < size; i++){
int[] cur = q.poll();
//System.out.println("cur: " + Arrays.toString(cur));
//System.out.println("target: " + Arrays.toString(target));
if (cur[0] == target[0] && cur[1] == target[1]) return step;
for (int j = 0; j < 4; j++){
int xx = cur[0] + x_moves[j];
int yy = cur[1] + y_moves[j];
int[] nei = {xx, yy};
if (xx < 0 || xx >= forest.size() || yy < 0 || yy >= forest.get(0).size() || visited[xx][yy] || forest.get(xx).get(yy) == 0) continue;
//seen.add(nei);
visited[xx][yy] = true;
q.offer(nei);
}
}
step++;
}
return -1;
}
}
490 The Maze
class Solution {
public boolean hasPath(int[][] maze, int[] start, int[] destination) {
if (maze == null || maze.length == 0) return false;
int n = maze.length, m = maze[0].length;
Queue<int[]> q = new LinkedList<>();
boolean[][] visited = new boolean[n][m];
q.offer(start);
visited[start[0]][start[1]] = true;
int[] x_moves = {0, 1, 0, -1};
int[] y_moves = {1, 0, -1, 0};
while (!q.isEmpty()){
int[] cur = q.poll();
int curX = cur[0];
int curY = cur[1];
//System.out.println("cur X: " + curX + " cur Y: " + curY);
if (curX == destination[0] && curY == destination[1]) return true;
for (int i = 0; i < 4; i++){
int newX = curX;
int newY = curY;
while (newX < n && newY < m){
newX += x_moves[i];
newY += y_moves[i];
//System.out.println("new X: " + newX + " new Y: " + newY);
if (newX >= n || newY >= m || newX < 0 || newY < 0) break;
if (maze[newX][newY] == 1) break;
}
newX -= x_moves[i];
newY -= y_moves[i];
if (!visited[newX][newY]){
q.offer(new int[]{newX, newY});
visited[newX][newY] = true;
}
}
}
return false;
}
}
505 The Maze II
similar to Trapping Rain Water II
class Solution {
private class DistancePoint{
int[] point;
int distance;
public DistancePoint(int[] point, int distance){
this.point = point;
this.distance = distance;
}
}
public int shortestDistance(int[][] maze, int[] start, int[] destination) {
if (maze == null || maze.length == 0) return -1;
int n = maze.length, m = maze[0].length;
PriorityQueue<DistancePoint> q = new PriorityQueue<>((a, b) -> (a.distance - b.distance));
int[][] visited = new int[n][m];
for (int i = 0; i < visited.length; i++){
Arrays.fill(visited[i], Integer.MAX_VALUE);
}
DistancePoint sourcePoint = new DistancePoint(start, 0);
int[] x_moves = {0, 1, 0, -1};
int[] y_moves = {1, 0, -1, 0};
q.offer(sourcePoint);
visited[start[0]][start[1]] = 0;
while (!q.isEmpty()){
DistancePoint cur = q.poll();
if (cur.point[0] == destination[0] && cur.point[1] == destination[1]) return cur.distance;
for (int i = 0; i < 4; i++){
int newX = cur.point[0];
int newY = cur.point[1];
int newDistance = cur.distance;
while (true){
newX += x_moves[i];
newY += y_moves[i];
newDistance += 1;
if (newX < 0 || newX >= n || newY < 0 || newY >= m || maze[newX][newY] == 1) break;
}
newX -= x_moves[i];
newY -= y_moves[i];
newDistance -= 1;
int[] newPoint = new int[]{newX, newY};
if (visited[newX][newY] > newDistance){
//System.out.println("newX: " + newX + " newY: " + newY);
q.offer(new DistancePoint(newPoint, newDistance));
visited[newX][newY] = newDistance;
}
}
}
return -1;
}
}
499 The Maze III
public class Solution {
class Point implements Comparable<Point> {
int x,y,l;
String s;
public Point(int _x, int _y) {x=_x;y=_y;l=Integer.MAX_VALUE;s="";}
public Point(int _x, int _y, int _l,String _s) {x=_x;y=_y;l=_l;s=_s;}
public int compareTo(Point p) {return l==p.l?s.compareTo(p.s):l-p.l;}
}
public String findShortestWay(int[][] maze, int[] ball, int[] hole) {
int m=maze.length, n=maze[0].length;
Point[][] points=new Point[m][n];
for (int i=0;i<m*n;i++) points[i/n][i%n]=new Point(i/n, i%n);
int[][] dir=new int[][] {{-1,0},{0,1},{1,0},{0,-1}};
String[] ds=new String[] {"u","r","d","l"};
PriorityQueue<Point> list=new PriorityQueue<>(); // using priority queue
list.offer(new Point(ball[0], ball[1], 0, ""));
while (!list.isEmpty()) {
Point p=list.poll();
if (points[p.x][p.y].compareTo(p)<=0) continue; // if we have already found a route shorter
points[p.x][p.y]=p;
for (int i=0;i<4;i++) {
int xx=p.x, yy=p.y, l=p.l;
while (xx>=0 && xx<m && yy>=0 && yy<n && maze[xx][yy]==0 && (xx!=hole[0] || yy!=hole[1])) {
xx+=dir[i][0];
yy+=dir[i][1];
l++;
}
if (xx!=hole[0] || yy!=hole[1]) { // check the hole
xx-=dir[i][0];
yy-=dir[i][1];
l--;
}
list.offer(new Point(xx, yy, l, p.s+ds[i]));
}
}
return points[hole[0]][hole[1]].l==Integer.MAX_VALUE?"impossible":points[hole[0]][hole[1]].s;
}
}