今天咱聊聊某啰的“早10晚8”考勤制度。这信息一出，我第一反应是：“这不就披着‘人性化’外衣的8小时工作制吗？”但细看，发现亮点和槽点真是一大堆。
算法题：离建筑物最近的距离
0表示空地，1表示建筑物，2表示障碍物。你需要找出每个空地到所有建筑物的最短距离之和。解法思路
初始化：创建两个网格， dist用来记录每个空地到建筑物的距离总和，reach记录每个空地被多少个建筑物触达。逐一BFS：从每个建筑物出发，用 BFS 遍历整个网格，更新空地的 dist和reach。遍历找结果：最后，遍历整个网格，找到所有被所有建筑物触达的空地，并返回最小的 dist值。
import java.util.*;
public class ShortestDistanceFromBuildings {
public int shortestDistance(int[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
int[][] dist = new int[rows][cols];
int[][] reach = new int[rows][cols];
int buildingCount = 0;
// Directions for BFS
int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// Step 1: Traverse the grid to start BFS from each building
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 1) { // Found a building
buildingCount++;
boolean[][] visited = new boolean[rows][cols];
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{i, j});
int level = 0;
while (!queue.isEmpty()) {
level++;
int size = queue.size();
for (int k = 0; k < size; k++) {
int[] curr = queue.poll();
for (int[] dir : directions) {
int x = curr[0] + dir[0];
int y = curr[1] + dir[1];
if (x >= 0 && x < rows && y >= 0 && y < cols &&
grid[x][y] == 0 && !visited[x][y]) {
dist[x][y] += level;
reach[x][y]++;
visited[x][y] = true;
queue.offer(new int[]{x, y});
}
}
}
}
}
}
}
// Step 2: Find the minimum distance
int minDist = Integer.MAX_VALUE;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 0 && reach[i][j] == buildingCount) {
minDist = Math.min(minDist, dist[i][j]);
}
}
}
return minDist == Integer.MAX_VALUE ? -1 : minDist;
}
}
代码解析
复杂度分析
时间复杂度： O(b * n * m)，其中b是建筑物的数量，n和m是网格的行和列。每个建筑物做一次 BFS，每次 BFS 遍历整个网格。空间复杂度： O(n * m)，需要额外的网格记录距离和访问状态。
一些小坑
障碍物问题：BFS 要跳过障碍物，否则会算到不合法的点。 无解的情况：如果某个空地无法被所有建筑物触达，要返回 -1。
-END-
以上，就是今天的分享了，看完文章记得右下角给何老师点赞，也欢迎在评论区写下你的留言。
