google面經

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

BFS方法找y，我没太想明白，大神们能给点思路么？

假设x = 0, y = 1. 只要把所有的0存入queue， 然后层遍历，每一层结果增加1， 遇到的第一个1就返回结果。

1. // 0 means x, 1 means y
   
2. int shortestDist(vector<vector<int>> & grid) {
   
3.     int m = grid.size(), n = grid[0].size(), res = 0;
   
4.     queue<pair<int, int>> q;
   
5.    
   
6.     for (int i = 0; i < m; ++i) {
   
7.         for (int j = 0; j < n; ++j) {
   
8.             if (grid[i][j] == 0) {
   
9.                 q.push({i, j});
   
10.             }
    
11.         }
    
12.     }
    
13.     while (!q.empty()) {
    
14.         int len = q.size();
    
15.         
    
16.         for (int i = 0; i < len; ++i) {
    
17.             auto r = q.front().first, c = q.front().second;
    
18.             q.pop();
    
19.             if (grid[r][c] == 1) return res;
    
20. 
    
21.             for (auto dir : dirs) {
    
22.                 int x = r + dir[0], y = c + dir[1];
    
23.                 if (x < 0 || x >= m ||  y < 0 || y >= n) continue;
    
24. 
    
25.                 q.push({x, y});
    
26.             }
    
27.         }
    
28.         ++res;
    
29.     }
    
30.     return -1;
    
31. }

复制代码

假设x = 0, y = 1, 扫一边矩阵把所有0的坐标存入queue中，然后层遍历，每一层增加一个结果。遇到当前格子是1的就直接返回结果。这样对吗？