Careercup – Google面试题 – 4716965625069568

2014-05-06 00:17

题目链接

原题：

Given a -D matrix represents the room, obstacle and guard like the following ( is room, B->obstacle, G-> Guard): B G G
B   calculate the steps from a room to nearest Guard and set the matrix, like this B G G
B
Write the algorithm, with optimal solution.

题目：有一个二维矩阵表示的迷宫，其中G表示保安人员，B表示不可穿越的墙，其他位置均为空地。如果每次可以向东南西北四个方向移动一格，请计算出每个空格离最近的保安有多远。题目给出了一个示例。

解法：既然矩阵里可能有多个保安，我的思路是以各个保安为中心，进行广度优先搜索，搜索的过程中随时更新每个空格位置的最短距离，保证全部搜索完之后所有的结果都是最小的。单次BFS的时间代价是O(n^2)级别的。

代码：

 // http://www.careercup.com/question?id=4716965625069568
 #include <queue>
 #include <vector>
 using namespace std; class Solution {
 public:
     void solve(vector<vector<int> > &matrix) {
         // -1 for guard
         // -2 for blockade
         // 0 for room
         // > 0 for distance         n = (int)matrix.size();
         if (n == ) {
             return;
         }
         m = (int)matrix[].size();
         if (m == ) {
             return;
         }         int i, j;         for (i = ; i < n; ++i) {
             for (j = ; j < m; ++j) {
                 if (matrix[i][j] == -) {
                     doBFS(matrix, i, j);
                 }
             }
         }
     };
 private:
     int n, m;     bool inBound(int x, int y) {
         return x >=  && x <= n -  && y >=  && y <= m - ;
     }     void doBFS(vector<vector<int> > &matrix, int x, int y) {
         queue<int> q;
         static int dd[][] = {{-, }, {+, }, {, -}, {, +}};
         int tmp;
         int xx, yy;
         int i;
         int dist;         q.push(x * m + y);
         while (!q.empty()) {
             tmp = q.front();
             q.pop();
             x = tmp / m;
             y = tmp % m;
             dist = matrix[x][y] >  ? matrix[x][y] : ;
             for (i = ; i < ; ++i) {
                 xx = x + dd[i][];
                 yy = y + dd[i][];
                 if (!inBound(xx, yy) || matrix[xx][yy] <  ||
                     (matrix[xx][yy] >  && matrix[xx][yy] <= dist + )) {
                     // out of boundary
                     // a guard or a blockade
                     // the distance is no shorter
                     continue;
                 }
                 matrix[xx][yy] = dist + ;
                 q.push(xx * m + yy);
             }
         }
     }
 };