洛谷原题:https://www.luogu.com.cn/problem/P1002
用的DP,但是WA,求指导
思路是把所有坐标+1(坐标原点映射到(1,1)),再用数组E[][]标记马可能在的地方(用in函数避免数组越界),最后dp
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
//f[i][j]表示走到(i,j)的总路径条数
//转移方程:f[i][j]=f[i][j-1]+f[i-1][j]
int Bx,By,Hx,Hy;
int f[22][22],E[22][22];
//坐标原点映射为(1,1)
//检查是否在边界内
bool in(int x,int y){
return x<1&&y<1?false:true;
}
int dp(int Bx,int By,int Hx,int Hy){
//马
memset(E,0,sizeof(E));
E[Hx][Hy]=-1;
for(int i=-2;i<=2;i+=4)for(int j=-1;i<=1;i+=2)if(in(Hx+i,Hy+j))E[Hx+i][Hy+j]=-1;
for(int i=-1;i<=1;i+=2)for(int j=-2;j<=2;j+=4)if(in(Hx+i,Hy+j))E[Hx+i][Hy+j]=-1;
//for(int i=1;i<=Bx;i++)f[i][1]=1;
//for(int j=1;j<=By;j++)f[1][j]=1;
f[1][0]=1;
for(int i=1;i<=Bx;i++){
for(int j=1;j<=By;j++){
if(E[i][j]==-1)f[i][j]=0;
else f[i][j]=f[i][j-1]+f[i-1][j];
}
}
return f[Bx][By];
}
int main(){
cin>>Bx>>By>>Hx>>Hy;
cout<<dp(Bx+1,By+1,Hx+1,Hy+1);
return 0;
}
return x<1&&y<1?false:true;
这意思要x和y都小于1才是false?应该是x<1 || y<1吧,有一个小于1就不对了吧