三刷 05/2022
Version #1 Matrix BFS
写了两个bug
一个是landInfos 的hash是next position的hash不应该用current position的hash
另外一个是(0, 0) 的hash value是0，恰好等于matrix的default value，导致(0, 0)点没法被BFS，所以要初始化成-1
Time O(M^2N^2)
Space O(MN)
Runtime: 674 ms, faster than 26.68% of Java online submissions for Shortest Distance from All Buildings.
Memory Usage: 145 MB, less than 15.34% of Java online submissions for Shortest Distance from All Buildings.
class Solution {
class LandInfo {
int buildingCount = 0;
int buildingDistance = 0;
public LandInfo() {}
}
private static int LAND = 0;
private static int BUILDING = 1;
private static int OBSTACLE = 2;
public int shortestDistance(int[][] grid) {
// Calculate all the building's distance to all land
if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
return -1;
}
int rows = grid.length;
int cols = grid[0].length;
// key-y*cols+x, value-LandInfo
Map<Integer, LandInfo> landInfos = new HashMap<>();
int[][] visited = new int[rows][cols];
for (int y = 0; y < rows; y++) {
for (int x = 0; x < cols; x++) {
visited[y][x] = -1;
}
}
int buildingCnt = 0;
for (int y = 0; y < rows; y++) {
for (int x = 0; x < cols; x++) {
if (grid[y][x] != BUILDING) {
continue;
}
buildingCnt++;
bfs(grid, visited, x, y, landInfos);
}
}
// System.out.println(buildingCnt);
Integer res = Integer.MAX_VALUE;
for (LandInfo info : landInfos.values()) {
// System.out.printf("buildingCnt %d, buildingDist %d\n", info.buildingCount, info.buildingDistance);
if (info.buildingCount == buildingCnt) {
res = Math.min(res, info.buildingDistance);
}
}
return res == Integer.MAX_VALUE ? -1 : res;
}
private int[] dx = new int[]{1, 0, -1, 0};
private int[] dy = new int[]{0, -1, 0, 1};
private void bfs(int[][] grid, int[][] visited, int x, int y, Map<Integer, LandInfo> landInfos) {
int rows = grid.length, cols = grid[0].length;
// System.out.printf("(%d, %d)\n", x, y);
int hash = y * cols + x;
Queue<int[]> que = new ArrayDeque<>();
que.offer(new int[]{x, y});
visited[y][x] = hash;
int dist = 0;
while (!que.isEmpty()) {
int size = que.size();
dist++;
while (size-- > 0) {
int[] curr = que.poll();
for (int i = 0; i < 4; i++) {
int nx = curr[0] + dx[i];
int ny = curr[1] + dy[i];
if (nx < 0 || nx >= cols || ny < 0 || ny >= rows) {
continue;
}
if (visited[ny][nx] != hash && grid[ny][nx] == LAND) {
// System.out.printf("hash=%d\n", hash);
int nHash = ny * cols + nx;
LandInfo info = landInfos.getOrDefault(nHash, new LandInfo());
info.buildingCount++;
info.buildingDistance += dist;
landInfos.put(nHash, info);
visited[ny][nx] = hash;
que.offer(new int[]{nx, ny});
}
}
}
}
}
}
// Start from a building, try to find its shortest path to every empty land on the grid
// Accumulate the shortest path of all buildings
// If an empty land can be reached by all buildings and its accumulated shortest path is minimum, return the value
22.15 %
class Solution {
private final int LAND = 0;
private final int BUILDING = 1;
private final int OBSTACLE = 2;
public int shortestDistance(int[][] grid) {
if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {
return -1;
}
int minPath = Integer.MAX_VALUE;
int rows = grid.length;
int cols = grid[0].length;
int[][] sp = new int[rows][cols];
// Count how many times it is visited
int[][] visitedCount = new int[rows][cols];
// Iterate
int buildingCount = 0;
for(int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == BUILDING) {
shortestDistanceHelper(grid, sp, visitedCount, new int[]{i, j});
buildingCount++;
}
}
}
for(int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == LAND && visitedCount[i][j] == buildingCount) {
minPath = Math.min(minPath, sp[i][j]);
}
}
}
return minPath == Integer.MAX_VALUE ? -1 : minPath;
}
private int[] dx = new int[]{1, 0, -1, 0};
private int[] dy = new int[]{0, -1, 0, 1};
// x -> coordinate[0], y -> coordinate[1]
private void shortestDistanceHelper(int[][] grid, int[][] sp, int[][] visitedCount, int[] coordinate) {
int cols = grid[0].length;
Set<Integer> visited = new HashSet<>();
Queue<int[]> que = new LinkedList<>();
// Mark start point as visited and add it into queue
que.offer(coordinate);
visited.add(coordinate[0] * cols + coordinate[1]);
int level = 0;
while (!que.isEmpty()) {
int size = que.size();
level++;
while (size-- > 0) {
int[] curr = que.poll();
// Tries to go to 4 directions
for (int i = 0; i < 4; i++) {
int x = curr[0] + dx[i];
int y = curr[1] + dy[i];
if(isValid(grid, visited, x, y)) {
que.offer(new int[]{x, y});
visited.add(x * cols + y);
visitedCount[x][y]++;
sp[x][y] += level;
}
}
}
}
}
private boolean isValid(int[][] grid, Set<Integer> visited, int x, int y) {
return x >= 0 && x < grid.length && y >= 0 && y < grid[0].length
&& grid[x][y] == LAND
&& !visited.contains(x * grid[0].length + y);
}
}
二刷
果然hard题还是有陷阱的
譬如corner case
0 2 1
1 0 2
0 1 0
这里的右上角building被block住了，所以无解
所以需要用一个全局的visited count来保证所有的empty space都是可以被所有的building reach的
Runtime: 28 ms, faster than 70.18% of Java online submissions for Shortest Distance from All Buildings.
Memory Usage: 38.9 MB, less than 74.09% of Java online submissions for Shortest Distance from All Buildings.
class Solution {
private int[] dx = new int[]{1, 0, -1, 0};
private int[] dy = new int[]{0, 1, 0, -1};
public int shortestDistance(int[][] grid) {
int buildingCount = 0;
int[][] visitedCount = new int[grid.length][grid[0].length];
for (int x = 0; x < grid.length; x++) {
for (int y = 0; y < grid[0].length; y++) {
if (grid[x][y] == 1) {
buildingCount++;
bfs(grid, visitedCount, x, y);
}
}
}
int sp = Integer.MIN_VALUE;
for (int x = 0; x < grid.length; x++) {
for (int y = 0; y < grid[0].length; y++) {
// System.out.printf("x: %d, y: %d, grid: %d\n", x, y, grid[x][y]);
if (grid[x][y] < 0 && visitedCount[x][y] == buildingCount) {
sp = Math.max(sp, grid[x][y]);
}
}
}
if (sp != Integer.MIN_VALUE) {
return Math.abs(sp);
}
return -1;
}
private void bfs(int[][] grid, int[][] visitedCount, int startX, int startY) {
boolean[][] visited = new boolean[grid.length][grid[0].length];
Queue<int[]> que = new LinkedList<>();
visited[startX][startY] = true;
que.offer(new int[]{startX, startY});
int step = 0;
while (!que.isEmpty()) {
step++;
int size = que.size();
while (size-- > 0) {
int[] curr = que.poll();
for (int i = 0; i < 4; i++) {
int x = curr[0] + dx[i];
int y = curr[1] + dy[i];
if (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length && grid[x][y] <= 0 && !visited[x][y]) {
visited[x][y] = true;
grid[x][y] = grid[x][y] - step;
que.offer(new int[]{x, y});
visitedCount[x][y]++;
}
}
}
}
}
}
No comments:
Post a Comment