关于一个求最短路径(不带权)的算法，初学算法，请多指教～！(200分)

关于一个求最短路径(不带权)的算法
'.'表示空格
'X'表示不可通过
'S'表示源点
'D'表示目标点
输入文件可能类似以下:
..S......
...X..X.D
........X
要求读入输入文件后，算法可以计算出从S到D的可行路径中最短的一条，并输出。(以sseeeeenne的方向字母输出,e,s,w,n表示东南西北)
算法最好用Pascal实现
呵呵 ，对算法不太熟悉，学了算法，但是不知道怎么应用。
开始考虑用Dijkstra算法实现，但是...hoho，没有写出来，
后来看到A*算法，也没有实现...
可能直接利用广度优先算法就能实现，但是...
呵呵，希望哪位朋友给我一个具体实现？谢谢！

hehe, 如果棋盘尺寸不大,是可以直接利用广度优先算法的.
等我一下先.

输入文件名为input.txt
program Chess;
{$APPTYPE CONSOLE}
uses
SysUtils;
const
MaxSize = 100;
InputFileName = 'Input.txt';
Move: array [1..4, 1..2] of Integer = ((0, 1), (1, 0), (0, -1), (-1, 0));
type
TNode = record
x, y: Integer;
d: Integer;
Father: Integer
end;

var
Maze: array [1..MaxSize, 1..MaxSize] of Boolean;
Dx, Dy: Integer;
List: array [1..MaxSize*MaxSize] of TNode;
Close, Open: Integer;
d: Integer;
NewNode: TNode;
Found: Boolean;
function Init: Boolean;
var
InputFile: Text;
s: string;
x, y: Integer;
begin
Found:=False;
Close:=0;
Open:=1;
List[Open].Father:=0;
x:=0;
Reset(InputFile, InputFileName);
while not Eof(InputFile)do
begin
ReadLn(InputFile, s);
Inc(x);
if (Length(s)>MaxSize) or (x>MaxSize) then
begin
WriteLn('Maze size error!');
Result:=False;
Exit
end;
WriteLn(s);
for y:=1 to Length(s)do
if UpCase(s[y])='X' then
Maze[x, y]:=False
else
begin
Maze[x, y]:=True;
if UpCase(s[y])='S' then
begin
List[Open].x:=x;
List[Open].y:=y
end
else
if UpCase(s[y])='D' then
begin
Dx:=x;
Dy:=y
end
end
end;
CloseFile(InputFile);
Result:=True
end;

procedure Print(Index: Integer);
begin
if List[Index].Father<>1 then
Print(List[Index].Father);
case List[Index].d of
1: Write('e');
2: Write('s');
3: Write('w');
4: Write('n')
end
end;

functiondo
uble(Node: TNode): Boolean;
var
i: Integer;
begin
Result:=False;
for i:=1 to Open-1do
if (List.x=Node.x) and (List.y=Node.y) then
begin
Result:=True;
Exit
end
end;

begin
if Init then
repeat
Inc(Close);
for d:=1 to 4do
begin
NewNode.x:=List[Close].x+Move[d, 1];
NewNode.y:=List[Close].y+Move[d, 2];
if (NewNode.x>0) and (NewNode.x<=MaxSize) and (NewNode.y>0) and (NewNode.y<=MaxSize)
and Maze[NewNode.x, NewNode.y] then
begin
NewNode.d:=d;
NewNode.Father:=Close;
Inc(Open);
List[Open]:=NewNode;
if (NewNode.x=Dx) and (NewNode.y=Dy) then
begin
Print(Open);
Found:=True
end
else
ifdo
uble(NewNode) then
Dec(Open)
end
end
until (Close=Open) or Found;
if not Found then
WriteLn('Not found!');
ReadLn
end.
多测测,找找Bug

看看我的方法。此程序在TP7.0下编译通过。你自己再测试一下。
const maxn=100;
type node=record
x,y:integer;
end;
var a:array[1..maxn,1..maxn] of integer;
b:array[1..maxn,1..maxn] of byte;
s,d:node;
n,m,i,j,k:integer;
c:char;
change:boolean;
procedure print(x,y:integer);
begin
if (x=s.x) and (y=s.y) then
exit else
case b[x,y] of
1:begin
print(x-1,y);
write('n');
end;
2:begin
print(x+1,y);
write('s');
end;
3:begin
print(x,y-1);
write('e');
end;
4:begin
print(x,y+1);
write('w');
end;
end;
end;

begin
{-----------------Input----------------------}
fillchar(a,sizeof(a),255);
assign(input,'in.txt');
reset(input);
n:=1;
while not eofdo
begin
m:=1;
while not eolndo
begin
read(c);
if c='.' then
else
if c='X' then
a[n,m]:=-2 else
if c='S' then
begin
s.x:=n;
s.y:=m;
end else
begin
d.x:=n;
d.y:=m;
end;
m:=m+1;
end;
readln;
n:=n+1;
end;
n:=n-1;
m:=m-1;
a[s.x,s.y]:=0;
{---------------------Main-----------------------------}
repeat
change:=false;
for i:=1 to ndo
for j:=1 to mdo
if a[i,j]<>-2 then
begin
if a[i,j]=-1 then
a[i,j]:=maxint;
if (i>1) and (a[i-1,j]>=0) then
if a[i,j]>a[i-1,j]+1 then
begin
a[i,j]:=a[i-1,j]+1;
b[i,j]:=1;
end;
if (i<n) and (a[i+1,j]>=0) then
if a[i,j]>a[i+1,j]+1 then
begin
a[i,j]:=a[i+1,j]+1;
b[i,j]:=2;
end;
if (j>1) and (a[i,j-1]>=0) then
if a[i,j]>a[i,j-1]+1 then
begin
a[i,j]:=a[i,j-1]+1;
b[i,j]:=3;
end;
if (j<m) and (a[i,j+1]>=0) then
if a[i,j]>a[i,j+1]+1 then
begin
a[i,j]:=a[i,j+1]+1;
b[i,j]:=4;
end;
if a[i,j]=maxint then
a[i,j]:=-1 else
change:=true;
end;
until not(true) or (a[d.x,d.y]>0);
{----------------------------print---------------------------------------}
if a[d.x,d.y]<0 then
write('no answer') else
print(d.x,d.y);
writeln;
end.

呵呵，AI_Player在动态规划上发挥，值得学习。呵呵。

呵呵，因为我的搜索学得很弱，只知道算法，很难写得出程序，还要向您多多学习呢！

hehe,AI兄用的还不是动态规划,有点象而已.
动态规划只要一次扫描,而您的算法竟然是
repeat

until 次扫描.

只是一种类似的思想，有说是DP的，有说是贪心的，要说广搜也说的过去，呵呵

呵呵，是呀,说法很难统一的,
虽然有时候明摆着是一样的算法,可就是各自坚持自己的名称.

一切法皆离言说而无实义。

谢谢各位的回答。
但是小弟刚刚学习算法，能否给点程序说明或者注释，呵呵，看不懂呀？！

呵呵，在南京吗?
面谈都很难讲清楚,何况在这儿.

由衷地感谢LeeChange
呵呵，我不在南京，在成都。
能否在程序中加一点注释，大概说明一下，使我看程序有个方向？这样就可以了。

如果你没接触过广度优先的话,程序注释一点用的没有.
得拿一张大纸画一棵大大大大的树才能讲清楚.

我的方法很容易看懂吧，就是在起点标0，然后相邻的4格标1，再把跟1相邻的标2……如果一个格子被重复标记，取小的那个，直到目标格被标上

to AI_Player:
你的程序我读了，有个地方老是不懂
a[n,n]是你存放相当于地图上各点的值,-2是障碍,-1是空格，0是源点
1)b是存放什么的??我知道是与移动方向相关。
但是b[i,j]=1是指什么，是向北移到(i,j)还是从(i,j)向北移动?
2)
if (j>1) and (a[i,j-1]>=0) then
if a[i,j]>a[i,j-1]+1 then
begin
a[i,j]:=a[i,j-1]+1;//重复点取值较小的那个
b[i,j]:=3;//j-1与这里的3有什么关系？
end;
能讲讲你程序中的这个判断吗？谢谢！

b[i,j]是表示(i,j)这个格子是经由哪个格子到达的
比如你举的那段例子，b[i,j]=3
那就是说(i,j)这个格子是经由(i,j-1)这个格子到达的
1，2，3，4分别表示n,s,e,w

UP!

to AI_Player:
谢谢你的回答，还要麻烦你一下：
你说的:
"b[i,j]=3那就是说(i,j)这个格子是经由(i,j-1)这个格子到达的
1，2，3，4分别表示n,s,e,w"
这里(i,j-1)->(i,j)应该是"向上"，即"n"，为什么是"3"("e"，向右?)

b[i,j]表示的是从哪个方向来,而不是向哪个方向去.
再有,你弄错了行列关系.