2014-05-06 07:11
原题：
Find a shortest path in a N*N matrix maze from (,) to (N,N), assume is passable, is not, 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)的。
代码：
// http://www.careercup.com/question?id=5634470967246848
#include <cstdio>
#include <queue>
#include <vector>
using namespace std; int main()
{
int n;
vector<vector<int> > v;
queue<int> q;
int i, j, k;
int x, y;
int dx, dy;
int d[][] = {
{-, },
{+, },
{, -},
{, +}
};
int back[] = {, , , };
vector<vector<int> > trace;
vector<int> path;
int tmp; while (scanf("%d", &n) == && n > ) {
v.resize(n);
trace.resize(n);
for (i = ; i < n; ++i) {
v[i].resize(n);
trace[i].resize(n);
} for (i = ; i < n; ++i) {
for (j = ; j < n; ++j) {
scanf("%d", &v[i][j]);
if (v[i][j] == ) {
dx = i;
dy = j;
}
}
} v[][] = -;
q.push();
while (v[dx][dy] > && !q.empty()) {
tmp = q.front();
q.pop();
i = tmp / n;
j = tmp % n;
for (k = ; k < ; ++k) {
x = i + d[k][];
y = j + d[k][];
if (x < || x > n - || y < || y > n - ) {
continue;
}
if (v[x][y] > ) {
v[x][y] = v[i][j] - ;
trace[x][y] = back[k];
q.push(x * n + y);
}
}
}
while (!q.empty()) {
q.pop();
} if (v[dx][dy] < ) {
x = dx;
y = dy;
while (x || y) {
path.push_back(x * n + y);
i = x + d[trace[x][y]][];
j = y + d[trace[x][y]][];
x = i;
y = j;
}
path.push_back();
while (!path.empty()) {
x = path.back() / n;
y = path.back() % n;
printf("(%d, %d)", x, y);
path.pop_back();
}
putchar('\n');
} else {
printf("Unreachable.\n");
} for (i = ; i < n; ++i) {
v[i].clear();
trace[i].clear();
}
v.clear();
trace.clear();
path.clear();
} return ;
}