洛谷练习（8.6）
题目
- P1002 过河卒
- 题目描述
- 思路
- 代码
P1002 过河卒
题目描述
棋盘中有一个马士兵不能经过马，也不能经过马走一步就能到的位置，计算到终点有几种可能
思路
士兵只能往右或者下走，所以最后一个位置只能从上或者左过去；可能性就dp[i][j]=d[i-1][j]+d[i][-1]，依次类推
代码
void solve()
{int a,b,c,d;//记得把int定义为long long,或者直接用long long 定义int dp[30][30];//记录路数int q[30][30]={0};//记录不能走的位置cin>>a>>b>>c>>d;a=a+2; b=b+2; c=c+2; d=d+2;//都加2 是因为马可能在最上面的一行，或者左面，+2让起点从2开始就不用考虑边界问题，所以后面循环也从2开始q[c-2][d-1]=1; q[c-1][d-2]=1;//走一次能到的位置q[c+2][d-1]=1; q[c+1][d-2]=1;q[c+2][d+1]=1; q[c+1][d+2]=1;q[c-2][d+1]=1; q[c-1][d+2]=1;q[c][d]=1;//马的位置dp[1][2]=1; //因为都是0，所以把起点上面或者左面的定位1for(int i=2;i<=a;i++){for(int j=2;j<=b;j++){if(q[i][j]==1){dp[i][j]=0; continue;}dp[i][j]=dp[i-1][j]+dp[i][j-1];}}cout<<dp[a][b];
}