WA了7遍；；；；；
万恶的题目啊！！！
说明啊。。
比如说如果马在3,2的话
它控制了2,0
那么3,0
4,0
……
都走不到了。。。。。
附上未修饰程序一枚
#include<cstdio>
#include<cstdlib>
#include<cmath>
#define max(a,b) a>b?a:b
typedef long long int longint;
using namespace std;
longint pic[20][20];
longint a,b,m,n;
int xxx(){
pic[m][n]=0;
for(longint x=-2;x<=2;x++){
if(x){
longint b1=3-abs(x),b2=-b1;
if(m+x>=0){
if(n+b1>=0) pic[m+x][n+b1]=0;
if(n+b2>=0) pic[m+x][n+b2]=0;
}
}
}
int i;
for(i=0;i<=a;i++) if(!pic[i][0]) break;
for(;i<=a;i++) pic[i][0]=0;
for(i=0;i<=b;i++) if(!pic[0][i]) break;
for(;i<=b;i++) pic[0][i]=0;
return 0;
}
int main(){
scanf("%I64d %I642d %I64d %I64d",&a,&b,&m,&n);
if(m+n==0||(m==2&&n==0)||(m==a&&n==b)) {printf("0");return 0;}
for(longint i=0;i<=19;i++)for(longint j=0;j<=19;j++)pic[i][j]=1;
xxx();
for(longint i=1;i<=a;i++)for(longint j=1;j<=b;j++){
if(pic[i][j])
pic[i][j]=pic[i-1][j]+pic[i][j-1];
}
printf("%I64d ",pic[a][b]);
return 0;
}

直接dp，状态转移:如果(i,j)能到达，f[i,j]:=f[i-1,j]+f[i,j-1],边界条件f[0,0]=1.
Const
xx:Array[1..8]Of integer=(2,2,-2,-2,1,1,-1,-1);
yy:Array[1..8]Of integer=(1,-1,1,-1,2,-2,2,-2);
Var
n,m,x,y,i,j:integer;
b:Array[-5..25,-5..25]Of boolean;
f:Array[-5..20,-5..20]Of longint;
Begin
readln(n,m,x,y);
fillchar(b,sizeof(b),True);
fillchar(f,sizeof(f),0);
For i:=1 To 8 Do
b[x+xx[i],y+yy[i]]:=False;
b[x,y]:=False;
f[0,0]:=1;
For i:=0 To n Do
For j:=0 To m Do
IF (i<>0)or(j<>0) Then
If b Then f:=f[i-1,j]+f[i,j-1];
writeln(f[n,m]);
End.

居然没有全0ms

01 #include

02 struct s

03 {

04 int x,y;

05 }queue[300];

06 int dirax[3]={0,0,1};

07 int diray[3]={0,1,0};

08 int dirbx[9]={0,-2,-1,1,2,2,1,-1,-2};

09 int dirby[9]={0,1,2,2,1,-1,-2,-2,-1};

10 int map[20][20]={0},n,m,k=0;

11 void knight(int xx,int yy)//确定马的控制点

12 {

13 int i,newx,newy;

14 map[xx][yy]=1;

15 for(i=1;i=0 && newx=0 && newy

来看看

点这里查看程序源码+详细题解

动规。DFS易超时

DFS应该能过的，

不过学了动归之后94秒杀了

递推最好

算法：DFS

刚学了动规 练练手

program malanguohezu;

var w:array[-1..100,-1..100] of int64;

flag:array[-1..100,-1..100] of boolean;

n,m,x,y,x1,x2,y1,y2:longint;

dx:array[1..8] of integer=(-2,-2,-1,1,2,2,1,-1);

dy:array[1..8] of integer=(-1,1,2,2,1,-1,-2,-2);

procedure init;

var i,j:longint;

begin

fillchar(w,sizeof(w),0);

fillchar(flag,sizeof(flag),false);

read(x1,y1);

read(x2,y2);

for i:=0 to x1 do

for j:=0 to y1 do

flag:=true;

flag[x2,y2]:=false;

for i:=1 to 8 do

flag[x2+dx[i],y2+dy[i]]:=false;

w[0,0]:=1;

for i:=1 to x1 do if flag then w:=w;

for j:=1 to y1 do if flag[0,j] then w[0,j]:=w[0,j-1];

end;

procedure dp;

var i,j:longint;

begin

for i:=1 to x1 do

for j:=1 to y1 do

if flag then

w:=w+w;

write(w[x1,y1]);

end;

begin

init;

dp;

end.

自己下的数据测过了啊，结果只有60分，求解……

#include

#include

#include

#include

#include

using namespace std;

long long dp[20][20];

int x,y;

void dfs(int x1,int y1)

{

if(dp[x1][y1]>0) return ;

if(abs(x1-x)==2 && abs(y1-y)==1) return ;

if(abs(x1-x)==1 && abs(y1-y)==2) return ;

if(x1==x && y1==y) return ;

if(x1>0) dfs(x1-1,y1);

if(y1>0) dfs(x1,y1-1);

dp[x1][y1]=dp[x1-1][y1]+dp[x1][y1-1];

}

int main()

{

int a,b;

scanf("%d%d",&a,&b);

scanf("%d%d",&x,&y);

dp[0][0]=1;

dfs(a,b);

printf("%d\n",dp[a]);

return 0;

}

dfs就行~

但是注意1.马本身不能被卒踏过（为此错了3次）

2.马控制点可能在边界或超出）

好吧。。提交的七八次才过。

这条题目用递推做效率极高

零秒闪过

但要注意的就是可能马在边界上或马的控制点不在地图上

这就要做一些处理防止数组下标越界和递推发生错误。。

递推公式：map[x,y]:=map[x-1,y]+map[x,y-1];

这里MAP我直接存放的的就是解的路径条数。。

在递推之前要把map[0,0]设置为1

具体程序贴上来。大牛莫喷。。

var map:array[-5..20,-5..20] of longint;

kz:array[-5..20,-5..20] of boolean;

x,y,mx,my,bx,by:integer;

begin

read(bx,by,mx,my);

fillchar(kz,sizeof(kz),true);

fillchar(map,sizeof(map),0);

map[0,0]:=1;

for x:=0 to 15 do

for y:=0 to 15 do

if ((x-mx)*(x-mx)+(y-my)*(y-my))=5 then kz[x,y]:=false;

kz[mx,my]:=false;

for x:=0 to 15 do

for y:=0 to 15 do

if kz[x,y] and not ((x=0) and (y=0))then

map[x,y]:=map[x-1,y]+map[x,y-1];

write(map[bx,by]);

end.

点击这里查看代码

虽然没有达到10个0ms，但毕竟AC了，10个0ms的解法可以上教辅资料上找

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 399ms

├ 测试数据 10：答案正确... 430ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：829ms

可恶，longint啊！integer去死，害我提交n次

..递归

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 274ms

├ 测试数据 10：答案正确... 352ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：626ms

const

dx:array[1..8] of integer=(-2,-1,1,2,2,1,-1,-2);

dy:array[1..8] of integer=(1,2,2,1,-1,-2,-2,-1);

var

a:array[-2..20,-2..20] of 0..1;

cou,n,m,x,y,i:longint;

procedure sod(x,y:integer);

begin

if (x

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 447ms

├ 测试数据 10：答案正确... 603ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1050ms

直接爆搜。。。。

如此水题 秒杀好简单~~~

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

var map:array[-2..20,-2..20] of boolean;

f:array[-2..20,-2..20] of longint;

x,y,m,n:integer;

begin

fillchar(map,sizeof(map),true);

fillchar(f,sizeof(f),0);

readln(m,n,x,y);

map[x,y]:=false;

map[x+1,y+2]:=false;map[x-1,y+2]:=false;

map[x+1,y-2]:=false;map[x-1,y-2]:=false;

map[x+2,y+1]:=false;map[x+2,y-1]:=false;

map[x-2,y+1]:=false;map[x-2,y-1]:=false;

f[0,0]:=1;

for x:=0 to m do

for y:=0 to n do

if (map[x,y]) and (not((x=0) and (y=0))) then f[x,y]:=f[x-1,y]+f[x,y-1];

writeln(f[m,n]);

end.

太水了

program p1121;

var

n,m,a1,a2,i,j:longint;

f:array[-6..30,-6..30] of longint;

ans:array[-6..30,-6..30] of boolean;

begin

read(n,m,a1,a2);

ans[a1,a2]:=true;

ans[a1-1,a2+2]:=true;ans[a1+1,a2+2]:=true;

ans[a1+2,a2+1]:=true;ans[a1+2,a2-1]:=true;

ans[a1-1,a2-2]:=true;ans[a1+1,a2-2]:=true;

ans[a1-2,a2+1]:=true;ans[a1-2,a2-1]:=true;

f[0,0]:=1;

for i:=0 to n do

for j:=0 to m do

begin

if ans=false then f:=f+f;

f[0,0]:=1;

end;

writeln(f[n,m]);

end.