Google 面试经验分享：房间到大门最短距离算法题 - Oavoservice
2025-07-03
🎤 Google 0703 面经
👩💻 Candidate 在 Google 面试中遇到了一个经典的房间到大门最短距离算法题。
📋 题目要求
给定一个由墙（'#'）、大门（'G'）和通道（'.'）组成的二维网格rooms，需要计算每个空通道到最近大门的最短距离，并将结果填入网格。
📝 具体说明
- '#' 表示墙，不能通过
- 'G' 表示大门，距离为0
- '.' 表示通道，需要计算到最近大门的距离
- 只能上下左右移动，不能斜向移动
- 如果通道无法到达任何大门，保持为'.'
❓ 问题分析
这是一个典型的多源最短路径问题：
- 核心思想：从所有大门同时开始BFS
- 关键点：使用队列存储所有大门位置
- 优化：可以原地修改网格，节省空间
💡 思路设计
使用多源BFS：
- 找到所有大门位置，加入队列
- 从队列中取出位置，检查四个方向
- 如果是通道，更新距离并加入队列
- 重复直到队列为空
💻 代码实现
import java.util.*;
public class RoomsDistanceCalculator {
// 方向数组：上、下、左、右
private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
// 方法1：多源BFS - 原地修改
public void calculateDistances(char[][] rooms) {
if (rooms == null || rooms.length == 0 || rooms[0].length == 0) {
return;
}
int m = rooms.length;
int n = rooms[0].length;
Queue<int[]> queue = new LinkedList<>();
// 找到所有大门，加入队列
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (rooms[i][j] == 'G') {
queue.offer(new int[]{i, j, 0}); // [row, col, distance]
}
}
}
// BFS遍历
while (!queue.isEmpty()) {
int[] current = queue.poll();
int row = current[0];
int col = current[1];
int distance = current[2];
// 检查四个方向
for (int[] dir : DIRECTIONS) {
int newRow = row + dir[0];
int newCol = col + dir[1];
// 边界检查和障碍物检查
if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n
&& rooms[newRow][newCol] == '.') {
// 更新距离
rooms[newRow][newCol] = (char) ('0' + distance + 1);
queue.offer(new int[]{newRow, newCol, distance + 1});
}
}
}
}
// 方法2：多源BFS - 使用额外距离数组
public int[][] calculateDistancesWithArray(char[][] rooms) {
if (rooms == null || rooms.length == 0 || rooms[0].length == 0) {
return new int[0][0];
}
int m = rooms.length;
int n = rooms[0].length;
int[][] distances = new int[m][n];
// 初始化距离数组
for (int i = 0; i < m; i++) {
Arrays.fill(distances[i], -1); // -1表示未访问
}
Queue<int[]> queue = new LinkedList<>();
// 找到所有大门
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (rooms[i][j] == 'G') {
distances[i][j] = 0;
queue.offer(new int[]{i, j});
}
}
}
// BFS遍历
while (!queue.isEmpty()) {
int[] current = queue.poll();
int row = current[0];
int col = current[1];
for (int[] dir : DIRECTIONS) {
int newRow = row + dir[0];
int newCol = col + dir[1];
if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n
&& rooms[newRow][newCol] == '.' && distances[newRow][newCol] == -1) {
distances[newRow][newCol] = distances[row][col] + 1;
queue.offer(new int[]{newRow, newCol});
}
}
}
return distances;
}
// 方法3：单源BFS - 对每个通道单独计算
public void calculateDistancesSingleSource(char[][] rooms) {
if (rooms == null || rooms.length == 0 || rooms[0].length == 0) {
return;
}
int m = rooms.length;
int n = rooms[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (rooms[i][j] == '.') {
int distance = bfsToNearestGate(rooms, i, j);
if (distance != Integer.MAX_VALUE) {
rooms[i][j] = (char) ('0' + distance);
}
}
}
}
}
private int bfsToNearestGate(char[][] rooms, int startRow, int startCol) {
int m = rooms.length;
int n = rooms[0].length;
boolean[][] visited = new boolean[m][n];
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{startRow, startCol, 0});
visited[startRow][startCol] = true;
while (!queue.isEmpty()) {
int[] current = queue.poll();
int row = current[0];
int col = current[1];
int distance = current[2];
if (rooms[row][col] == 'G') {
return distance;
}
for (int[] dir : DIRECTIONS) {
int newRow = row + dir[0];
int newCol = col + dir[1];
if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n
&& !visited[newRow][newCol] && rooms[newRow][newCol] != '#') {
visited[newRow][newCol] = true;
queue.offer(new int[]{newRow, newCol, distance + 1});
}
}
}
return Integer.MAX_VALUE; // 无法到达任何大门
}
// 辅助方法：打印网格
public void printGrid(char[][] rooms) {
for (char[] row : rooms) {
for (char cell : row) {
System.out.print(cell + " ");
}
System.out.println();
}
System.out.println();
}
// 测试方法
public static void main(String[] args) {
RoomsDistanceCalculator calculator = new RoomsDistanceCalculator();
// 测试用例1：基本网格
char[][] rooms1 = {
{'#', '#', '#', '#', '#'},
{'#', '.', '.', 'G', '#'},
{'#', '.', '#', '.', '#'},
{'#', 'G', '.', '.', '#'},
{'#', '#', '#', '#', '#'}
};
System.out.println("原始网格1：");
calculator.printGrid(rooms1);
calculator.calculateDistances(rooms1);
System.out.println("计算距离后：");
calculator.printGrid(rooms1);
// 测试用例2：复杂网格
char[][] rooms2 = {
{'#', '#', '#', '#', '#', '#', '#'},
{'#', '.', '.', '.', '.', '.', '#'},
{'#', '.', '#', '.', '#', '.', '#'},
{'#', '.', '.', 'G', '.', '.', '#'},
{'#', '#', '#', '#', '#', '#', '#'}
};
System.out.println("原始网格2：");
calculator.printGrid(rooms2);
calculator.calculateDistances(rooms2);
System.out.println("计算距离后：");
calculator.printGrid(rooms2);
}
}🔍 算法分析
- 多源BFS时间复杂度：O(m*n)，其中m和n是网格的行数和列数
- 单源BFS时间复杂度：O(k*m*n)，其中k是通道数量
- 空间复杂度：O(m*n)（队列空间）
- 核心思想：多源BFS + 最短路径
📊 测试用例
// 测试用例1：基本网格
原始网格：
# # # # #
# . . G #
# . # . #
# G . . #
# # # # #
期望输出：
# # # # #
# 3 2 1 #
# 2 # 1 #
# 1 1 2 #
# # # # #
// 测试用例2：复杂网格
原始网格：
# # # # # # #
# . . . . . #
# . # . # . #
# . . G . . #
# # # # # # #
期望输出：
# # # # # # #
# 3 2 1 2 3 #
# 2 # 1 # 2 #
# 1 1 0 1 1 #
# # # # # # #🚀 优化思路
面试官可能会问如何优化：
- 原地修改：直接在原网格上修改，节省空间
- 多源BFS：比单源BFS效率更高
- 边界检查优化：提前检查边界条件
✨ 面试官反馈
面试官对解决方案很满意："Excellent! You've provided multiple approaches including the optimal multi-source BFS. The code is clean and handles edge cases well. Great understanding of graph algorithms!"
面试技巧分享
在 Google 面试中，除了算法实现，面试官还会关注：
1. 问题建模能力
能够将二维网格问题抽象为图论问题，建立正确的数学模型。
2. 多种解法对比
提供多源BFS、单源BFS等多种解法，并分析其优缺点。
3. 边界条件处理
考虑空网格、无大门、无法到达等特殊情况。
4. 空间优化思维
主动思考如何优化空间复杂度，如原地修改。
Oavoservice 实时辅助服务
在这次 Google 面试中，我们的实时辅助系统发挥了关键作用：
- 问题分析：帮助候选人快速识别多源最短路径问题的本质
- 算法指导：提供多源BFS的核心思路
- 代码实现：协助完成完整的代码实现
- 测试验证：确保所有测试用例都能正确通过
结语
房间到大门最短距离是一道经典的图论问题，考察候选人对BFS算法、多源最短路径的理解。在面试中，能够提供多种解法并分析其优缺点，展现了候选人的技术深度和算法思维。
如果你正在准备 Google 或其他公司的技术面试，欢迎联系 Oavoservice。我们拥有丰富的面试经验和专业的辅助团队，能够在你最需要的时候提供及时有效的帮助。
Oavoservice - 让每一次面试都成为成功的机会！
需要辅助的同学随时dd哦，vo开始前支持mock！