【题目描述】
棋盘上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点的路径的条数。 【输入样例】【输出样例】 |
#include <bits/stdc++.h>
using namespace std;
int h_d[9][2]={{0,0},{-1,-2},{1,-2},{-1,2},{1,2},{2,-1},{-2,-1},{2,1},{-2,1}};
int s_d[2][2]={{0,1},{1,0}};
long long a[100][100];
bool h[100][100];
long long ans=0;
using namespace std;
int n,m,ex,ey;
/*
void dfs(int x,int y)
{if(x==n&&y==m){ans++;return;}for(int i=0;i<2;i++){int nx=x+s_d[i][0]; int ny=y+s_d[i][1]; if(nx>=0&&nx<=n&&ny>=0&&ny<=m && a[nx][ny]==0 ) //可通行 dfs(nx,ny); }
}*/
int main()
{cin>>n>>m>>ex>>ey;memset(a,0,sizeof(a));memset(h,false,sizeof(h));for(int i=0;i<9;i++){int nx = ex + h_d[i][0];int ny= ey + h_d[i][1];if(nx>=0&&nx<=n&&ny>=0&&ny<=m)h[nx][ny]=true;}//dfs(0,0);//实际上a[0][0]点可以有两种走法但初始化他为1 是因为a[0][1]的走法只有一种且等于a[0][0] 同理 a[1][0]的走法只有一种且 等行a[0][0]a[0][0]=1;for(int i=0;i<=n;i++){for(int j=0;j<=m;j++){ if(h[i][j]==true) //马的控制点 continue;if(i==0&&j==0)continue;else if(i-1>=0&&j-1>=0)a[i][j]=a[i][j-1]+a[i-1][j]; //当前的走法等 于左边或从上面走法之和 else if(i-1<0) //边界只有上，没有左，即在第一列 a[i][j]=a[i][j-1];elsea[i][j]=a[i-1][j]; //边界只有左，没有上，即在最后行 }} //cout<<ans<<endl;cout<<a[n][m];return 0;
}
