Careercup

2014-05-06 07:11

原题：

Find a shortest path in a N*N matrix maze from (0,0) to (N,N), assume 1 is passable, 0 is not, 3 is destination, use memorization to cache the result. Here is my code. I am not sure if I am caching it right.

题目：给定一个N * N的矩阵，找出从(0, 0)到(n - 1, n - 1)的最短路径。此人在后面还贴上了自己的代码，从代码水平上看此人实力基本不足以参加Google的面试，此人叫“Guy”。

解法：对于这种移动距离限于一格的最短路径问题，最直接的思想就是BFS了。而这位老兄居然还把自己四路DFS的代码贴出来，多余的也就没必要评论了。此题要求得到完整的最短路径，所以进行BFS的同时，需要记录每个点的回溯位置。这样就可以从目的地一直回溯到出发点，得到一条完整的最短路径。算法的整体时间复杂度是O(n^2)的。

代码：

  1 // http://www.careercup.com/question?id=5634470967246848
  2 #include <cstdio>
  3 #include <queue>
  4 #include <vector>
  5 using namespace std;
  6 
  7 int main()
  8 {
  9     int n;
 10     vector<vector<int> > v;
 11     queue<int> q;
 12     int i, j, k;
 13     int x, y;
 14     int dx, dy;
 15     int d[4][2] = {
 16         {-1, 0}, 
 17         {+1, 0}, 
 18         {0, -1}, 
 19         {0, +1}
 20     };
 21     int back[4] = {1, 0, 3, 2};
 22     vector<vector<int> > trace;
 23     vector<int> path;
 24     int tmp;
 25     
 26     while (scanf("%d", &n) == 1 && n > 0) {
 27         v.resize(n);
 28         trace.resize(n);
 29         for (i = 0; i < n; ++i) {
 30             v[i].resize(n);
 31             trace[i].resize(n);
 32         }
 33         
 34         for (i = 0; i < n; ++i) {
 35             for (j = 0; j < n; ++j) {
 36                 scanf("%d", &v[i][j]);
 37                 if (v[i][j] == 3) {
 38                     dx = i;
 39                     dy = j;
 40                 }
 41             }
 42         }
 43         
 44         v[0][0] = -1;
 45         q.push(0);
 46         while (v[dx][dy] > 0 && !q.empty()) {
 47             tmp = q.front();
 48             q.pop();
 49             i = tmp / n;
 50             j = tmp % n;
 51             for (k = 0; k < 4; ++k) {
 52                 x = i + d[k][0];
 53                 y = j + d[k][1];
 54                 if (x < 0 || x > n - 1 || y < 0 || y > n - 1) {
 55                     continue;
 56                 }
 57                 if (v[x][y] > 0) {
 58                     v[x][y] = v[i][j] - 1;
 59                     trace[x][y] = back[k];
 60                     q.push(x * n + y);
 61                 }
 62             }
 63         }
 64         while (!q.empty()) {
 65             q.pop();
 66         }
 67         
 68         if (v[dx][dy] < 0) {
 69             x = dx;
 70             y = dy;
 71             while (x || y) {
 72                 path.push_back(x * n + y);
 73                 i = x + d[trace[x][y]][0];
 74                 j = y + d[trace[x][y]][1];
 75                 x = i;
 76                 y = j;
 77             }
 78             path.push_back(0);
 79             while (!path.empty()) {
 80                 x = path.back() / n;
 81                 y = path.back() % n;
 82                 printf("(%d, %d)", x, y);
 83                 path.pop_back();
 84             }
 85             putchar('
');
 86         } else {
 87             printf("Unreachable.
");
 88         }
 89         
 90         for (i = 0; i < n; ++i) {
 91             v[i].clear();
 92             trace[i].clear();
 93         }
 94         v.clear();
 95         trace.clear();
 96         path.clear();
 97     }
 98     
 99     return 0;
100 }