返回信息流如题，比如一个64格的正方形，求两点之间的最短路径。并且在正方形内有若干格子是障碍物，无法通过，请问该如何编程呢？多谢帮助
这是一条镜像帖。来源：北邮人论坛 / dot-net / #3666同步于 2012/4/12
该镜像源已超过 30 天没有更新，可能在源站已被删除。
dotNET机器人发帖
请教C#里算正方形格子里任意两点之间最短路径怎么求？
zj1991
2012/4/12镜像同步6 回复
订阅后，新回复会通过你的通知中心匿名送达。
6 条回复
【 在 zj1991 的大作中提到: 】
: 如题，比如一个64格的正方形，求两点之间的最短路径。并且在正方形内有若干格子是障碍物，无法通过，请问该如何编程呢？多谢帮助
using System;
namespace ConsoleApplication1 {
class Program {
static int m, n, nn, dx, dy, ex, ey;
static bool[][] xx, r;
static int MAX = 1 << 29;
// 输入 第一行有6个数，m，n，dx，dy，ex，ey。
// m, n 为区域大小，m行，n列
// dx, dy 为起点坐标，1<=dx<=m，1<=dy<=n
// ex, ey 为终点坐标，1<=ex<=m，1<=ey<=n
// 第2至m+1行，每行n个数，若为1，表示该位置不能通过，否则可通过
// 输出 仅一行，为从起点到终点的最短距离。若不能通过，输出-1。
// 样例输入：
// 4 4 1 1 1 4
// 0 1 1 0
// 0 1 0 0
// 0 1 1 0
// 0 0 0 0
// 样例输出：
// 9
static void Main(string[] args) {
string[] tokens = Console.ReadLine().Split(' ');
m = int.Parse(tokens[0]);
n = int.Parse(tokens[1]);
dx = int.Parse(tokens[2]) - 1;
dy = int.Parse(tokens[3]) - 1;
ex = int.Parse(tokens[4]) - 1;
ey = int.Parse(tokens[5]) - 1;
// xx记录各位置是否可通过
xx = new bool[m][];
for (int i = 0; i < m; i++) {
tokens = Console.ReadLine().Split(' ');
xx[i] = new bool[n];
for (int j = 0; j < n; j++)
xx[i][j] = int.Parse(tokens[j]) == 1;
}
nn = m * n;
// r记录各点之间的连接情况
r = new bool[nn][];
for (int i = 0; i < nn; i++) r[i] = new bool[nn];
for (int i = 0; i < m; i++) for (int j = 0; j < n; j++)
if (!xx[i][j]) {
if (i > 0 && !xx[i - 1][j]) r[i * n + j][(i - 1) * n + j] = true;
if (j > 0 && !xx[i][j - 1]) r[i * n + j][i * n + j - 1] = true;
if (i < m - 1 && !xx[i + 1][j]) r[i * n + j][(i + 1) * n + j] = true;
if (j < n - 1 && !xx[i][j + 1]) r[i * n + j][i * n + j + 1] = true;
}
Console.WriteLine(SPFA_SLF(dx * n + dy, ex * n + ey));
}
// SLF优化的SPFA算法，di为起点，dj为终点，返回起点到终点的最短距离
// dist记录各点到起点的当前估计最短距离
// q为用以进行松弛操作的节点队列
// v表示节点是否在队列中
// h队列起点，l队列长度
static int SPFA_SLF(int di, int dj) {
int[] dist = new int[nn], q = new int[nn];
bool[] v = new bool[nn];
int h = 0, l = 1, x;
for (int i = 0; i < nn; i++)
dist[i] = MAX;
dist[di] = 0; q[0] = di; v[di] = true;
while (l != 0) {
// 取队首节点
x = q[h]; v[q[h]] = false; l--; h = (h + 1) % nn;
for (int i = 0; i < nn; i++) {
if (r[x][i] && dist[x] + 1 < dist[i]) {
dist[i] = dist[x] + 1;
if (!v[i])
// 如果当前节点到起点距离较小，加入队首，否则加入队尾
if (l != 0 && dist[i] < dist[q[h]]) {
h = (h + nn - 1) % nn; l++; q[h] = i; v[i] = true;
} else {
q[(h + l++) % nn] = i; v[i] = true;
}
}
}
}
return dist[dj] == MAX ? -1 : dist[dj];
}
}
}
【 在 stczhc 的大作中提到: 】
:
: [code=csharp]
: using System;
: ...................
多谢大牛啊
【 在 stczhc 的大作中提到: 】
:
: [code=csharp]
: using System;
: ...................
问题补充：怎么样把最短路径的轨迹输出出来呢？
【 在 stczhc 的大作中提到: 】
:
: [code=csharp]
: using System;
: ...................
同学你好，我QQ847600517，可以加你的QQ咨询你一些C#的问题么？谢谢了