Question

pascal 编程题：骑士游历 急！！！！

骑士游历
问题描述：如下图所示有m*n一个棋盘，在棋盘左下角的A（1,1）点，有一个中国象棋〈马〉，并约定马走的规则：
①走日字；②只能向右走。
找出从A点（1,1）到B点(m,n )的路径条数。

输入：8 9
输出：10
最好输出所有路径条数及所有路径。
输出路径条数及任意一条具体路径。

Answer 1

const dx:array[1..4] of integer=(2,2,1,1);
dy:array[1..4] of integer=(1,-1,2,-2);
type map=record
x,y:integer;
end;
var I,n,m:integer; a:array[0..50] of map;
procedure dfs(i:integer);
var j:integer;
begin
for j:=1 to 4 do
if (a[i-1].x+dx[j]>0) and (a[i-1].x+dx[j]<=n) and (a[i-1].y+dy[j]>0) and (a[i-1].y+dy[j]<=m) then {判断是否在棋盘上}
begin a.x:=a[i-1].x+dx[j];
a.y:=a[i-1].y+dy[j];
if (a.x=n) and (a.y=m) then
begin write(‘(‘,1,’,’,1,’)’);
for j:=2 to I do write(‘->(’,a[j].x,’,’,a[j].y,’)’);
halt;{输出结果并退出程序}
end;
dfs(i+1);{搜索下一步}
a.x:=0;a.j:=0;
end;
end;
begin
a[1].x:=1;a[1].y:=1;
readln(n,m);
dfs(2);
writeln(‘no’);
end.

Answer 2

双重循环堆栈

Answer 3

这是回溯的经典题型，网上有很多解法，你可以去看看

Answer 4

var
p,d:array[0..10]of real;
n:longint;
d1,c,d2:real;
procedure init;
var
i:longint;
begin
readln(d1,c,d2,p[0],n);
for i:=1 to n do
readln(d[i],p[i]);
end;
procedure qs(l,r:longint);
var
i,j:longint;
k,t:real;
begin
i:=l;j:=r;k:=d[(i+j) div 2];
repeat
while d[i]<k do inc(i);
while d[j]>k do dec(j);
if i<=j then
begin
t:=d[i];d[i]:=d[j];d[j]:=t;
t:=p[i];p[i]:=p[j];p[j]:=t;
inc(i);dec(j);
end;
until i>j;
if i<r then qs(i,r);
if l<j then qs(l,j);
end;
procedure main;
var
i,pre,t:longint;
min,v,s:real;
begin
pre:=0;s:=0;v:=0;
repeat
i:=pre+1;
while (p[i]>p[pre]) and (i<=n) and not(d[pre]+c*d2<d[i]) do
inc(i);
if (i<=n) and (d[pre]+c*d2>=d[i])
then begin

if (d[i]-d[pre])/d2>v then
begin
s:=s+((d[i]-d[pre])/d2-v)*p[pre];
v:=0;
end
else v:=v-(d[i]-d[pre])/d2;
pre:=i;
end
else begin
if d[pre]+c*d2>=d1 then
begin
s:=s+((d1-d[pre])/d2-v)*p[pre];
writeln(s:0:2);
exit;
end;

t:=0;min:=maxlongint;
for i:=pre+1 to n do
if d[pre]+c*d2<d[i] then break
else if p[i]<min then begin
t:=i;
min:=p[i];
end;
if t=0 then begin
writeln('No Solution');
exit;
end;
s:=s+(c-v)*p[pre];
v:=c;
v:=v-(d[t]-d[pre])/d2;
pre:=t;
end;
until false;
end;
begin
init;
qs(1,n);
main;
end.