信息学奥赛一本通T1314：递推算法 过河卒
【题目描述】棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上的某一点有一个对方的马（如C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点，如图3-1中的C点和P1，……，P8，卒不能通过对方马的控制点。棋盘用坐标表示，A点(0,0)、B点(n, m) (n,m为不超过20的整数),同样马的位置坐标是需要给出的，C≠A且C≠B。现在要求你计算出卒从A
信息学奥赛一本通T1314：过河卒
【题目描述】
棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上的某一点有一个对方的马（如C点），该马所在的点和所有跳跃一步可达的点称为对方马的控制点，如图3-1中的C点和P1，……，P8，卒不能通过对方马的控制点。棋盘用坐标表示，A点(0,0)、B点(n, m) (n,m为不超过20的整数),同样马的位置坐标是需要给出的，C≠A且C≠B。现在要求你计算出卒从A点能够到达B点的路径的条数。
【输入】
给出n、m和C点的坐标。
【输出】
从A点能够到达B点的路径的条数。
【输入样例】
8 6 0 4
【输出样例】
1617
【源程序】
#include<iostream>
#include<cstring>
using namespace std;
long long a[30][30];
int vis[30][30];
int next[][2]={{2,1},{1,2},{-1,2},{-2,1},{-2,-1},{-1,-2},{1,-2},{2,-1}};
int main()
{
int n,m;
int x,y;
int nx,ny;
int i,j;
memset(vis,0,sizeof(vis));
cin>>n>>m>>x>>y;
a[0][0]=0;//处理A=B的情况
vis[x][y]=1;//设置马管辖的位置
a[x][y]=0;
for(i=0;i<8;i++)
{
nx=x+next[i][0];
ny=y+next[i][1];
if(0<=nx&&nx<=n&&0<=ny&&ny<=m)
{
vis[nx][ny]=1;
a[nx][ny]=0;
}
}
for(i=0;i<=n;i++)
{
if(vis[i][0]==1)
while(i<=n)
{
i++;
a[i][0]=0;
}
else
a[i][0]=1;
}
for(j=0;j<=m;j++)
{
if(vis[0][j]==1)
while(j<=m)
{
j++;
a[0][j]=0;
}
else
a[0][j]=1;
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(vis[i][j]==0)
a[i][j]=a[i][j-1]+a[i-1][j];
cout<<a[n][m]<<endl;
return 0;
}
信息学奥赛一本通T1314：递推算法 过河卒 归属于 递推算法，更多同类题解源程序见：递推算法 和 过河卒
- 发表于 2020-05-08 16:20
- 阅读 ( 1168 )
- 分类：信息学奥赛一本通
轩爸
0 篇文章
作家榜 »
-
admin
2 文章
-
张芳
0 文章
-
hanna
0 文章
-
Jason
0 文章
-
lixiaioqian
0 文章
-
GeraldWrora
0 文章
-
董伟
0 文章
-
信奥达人
0 文章
