pascal 迷宫路径问题

来源：百度知道 编辑：UC知道 时间：2024/05/18 01:46:16
描述 猩猩来到一个点（1，1），想吃右下角（N,N）的香蕉，规定只能往下走或者往右走，试问有多少种走法？
输入格式 第一行为一个整数N（N<=20)以下是一个N*N的正方形表示迷宫
输出格式 仅有一个数，表示路径总数，如果走不通，则输出0
样例输入 样例输出
2 2
0 0
0 0

var a:array[-1..21,-1..21] of longint;
n,i,j:longint;
begin
readln(n);
for i;=1 to n do
for j:=1 to n do
begin
read(t);
if t=0 then a[i,j]:=1
else a[i,j]:=0;
end;
for i;=1 to n do begin a[i,0]:=0; a[0,i]:=0;end;
a[0,1]:=1;
for i:=1 to n do
for j:=1 to n do
if a[i,j]=1 then a[i,j]:=a[i-1,j]+a[i,j-1];
writeln(a[n,n]);
end.

声明两个数组 第一个记录迷宫 第二个记录每一格的路径总数 比如一个
0 0 1
1 0 0
0 0 0
这样的迷宫 存在A数组里就是A[1，1]=0 A[1，2]=0等等 数组操作你会的吧？
然后对数组B进行操作：
首先在左上角的一格 只有一条路 所以B[1，1]=1
然后看B[1，2] 它可以由左面一格过来所以
B[1，2]=B[1，1]
依次类推到B[3，3]=B[3，2]+B[2，3]{左面一格的路径加上面一格的路径数。因为它可以由上面来也可以由左面来}

非常简单的递推
f[i,j]:=f[i-1,j]+f[i,j-1]