Google 12/01 onsite面经

Onsite 1, 一遍BFS

1. struct point {
   
2.     int x, y;
   
3. 
   
4.     point(int a, int b): x(a), y(b) {}
   
5. };
   
6. 
   
7. vector<vector<int>> bfs(vector<vector<char>> &map)
   
8. {
   
9.     size_t row = map.size();
   
10.     size_t col = map[0].size();
    
11. 
    
12.     vector<vector<int>> result;
    
13.     for (size_t i = 0; i < row; i++)
    
14.         result.push_back(vector<int>(col));
    
15. 
    
16.     queue<point> q;
    
17. 
    
18.     for (size_t i = 0; i < row; i++) {
    
19.         for (size_t j = 0; j < col; j++) {
    
20.             if (map[i][j] == 'G') {
    
21.                 point p(i, j);
    
22.                 q.push(p);
    
23.                 result[i][j] = -2;
    
24.             }
    
25.         }
    
26.     }
    
27. 
    
28.     //up, down, left, right
    
29.     vector<vector<int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
30. 
    
31.     int d = 1;
    
32.     while (!q.empty()) {
    
33.         size_t size = q.size();
    
34.         for (size_t i = 0; i < size; i++) {
    
35.             point p = q.front(); q.pop();
    
36. 
    
37.             for (auto dir : directions) {
    
38.                 int x = p.x + dir[0];
    
39.                 int y = p.y + dir[1];
    
40. 
    
41.                 if (x >= 0 && x < row && y >= 0 && y < col) {
    
42.                     if (map[x][y] == '.') {
    
43.                         if (result[x][y] == 0) {
    
44.                             result[x][y] = d;
    
45.                             q.push(point(x, y));
    
46.                         }
    
47.                     } else if (map[x][y] == 'L')
    
48.                         result[x][y] = -1;
    
49.                 }
    
50. 
    
51.             }
    
52.         }
    
53. 
    
54.         d++;
    
55.     }
    
56. 
    
57.     return result;
    
58. }
    
59. 
    
60. int main()
    
61. {
    
62.     vector<vector<char>> map = {
    
63.         {'G', 'L', 'L', '.'},
    
64.         {'.', '.', 'G', '.'},
    
65.         {'L', '.', 'L', '.'},
    
66.         {'.', 'G', 'L', 'G'},
    
67.         {'.', '.', '.', '.'},
    
68.     };
    
69. 
    
70.     vector<vector<int>> result = bfs(map);
    
71.     for (size_t i = 0; i < result.size(); i++) {
    
72.         for (size_t j = 0; j < result[0].size(); j++) {
    
73.             cout << result[i][j] << " ";
    
74.         }
    
75.         cout << endl;
    
76.     }
    
77. 
    
78.     return 0;
    
79. }

复制代码

膜一发～～