马拦过河卒

棋盘上A点有一个过河卒需要走到目标B点。卒行走的规则可以向下、或者向右。同时在棋盘上C点有一个对方的马该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。棋盘用坐标表示A点00、B点nmnm为不超过15的整数同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数假设马的位置是固定不动的并不是卒走一步马走一步。输入格式:一行四个数据用空格分隔分别表示B点的坐标和马的坐标。输出格式:一个数据表示所有的路径条数。输入样例:6 6 3 3输出样例:6答案#includestdio.h int main(){ // a,b棋盘右下角坐标(终点) // c,d马骑士所在的坐标 int a,b,c,d; // 输入棋盘终点坐标、马的坐标 scanf(%d %d %d %d,a,b,c,d); // arr 用来存路径数arr[i][j] 表示从(0,0)走到(i,j)的路径条数 int arr[20][20]{0}; // grr 标记障碍点1 表示该位置不能走马的位置 马能跳到的位置 int grr[20][20]{0}; // 先把马自己的位置标记为障碍 grr[c][d]1; // 马走日字的8个方向偏移量 // dx[]行偏移 dy[]列偏移 int dx[]{1,1,-1,-1,2,2,-2,-2}; int dy[]{2,-2,2,-2,1,-1,1,-1}; // 遍历8个方向标记马能跳到的所有位置为障碍 for(int i0;i8;i){ // 计算马下一步跳到的坐标 int x c dx[i]; int y d dy[i]; // 坐标合法在棋盘范围内 0xa 0yb if(x0 xa y0 yb){ grr[x][y] 1; // 标记为障碍物不能走 } } // 起点(0,0)路径数初始化为1自己到自己只有1种走法 arr[0][0] 1; // 遍历棋盘每一个坐标点 q行 w列 for(int q0;qa;q){ for(int w0;wb;w){ // 如果当前点是障碍物直接跳过不计算路径 if(grr[q][w]){ continue; } // 路径递推只能从 上方 或 左方 走过来 // 如果不是第一行可以从上面(q-1,w)走下来 if(q0){ arr[q][w] arr[q-1][w]; } // 如果不是第一列可以从左边(q,w-1)走过来 if(w0){ arr[q][w] arr[q][w-1]; } } } // 输出从(0,0)走到终点(a,b)的总路径数 printf(%d,arr[a][b]); return 0; }