马拦过河卒
棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。
棋盘用坐标表示，A点（0，0）、B点（n，m）（n，m为不超过15的整数），同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。
输入格式:
一行四个数据，用空格分隔，分别表示B点的坐标和马的坐标。
输出格式:
一个数据，表示所有的路径条数。
输入样例:
6 6 3 3输出样例:
6答案：
#include<stdio.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 i=0;i<8;i++){ // 计算马下一步跳到的坐标 int x = c + dx[i]; int y = d + dy[i]; // 坐标合法：在棋盘范围内 0<=x<=a 0<=y<=b if(x>=0 && x<=a && y>=0 && y<=b){ grr[x][y] = 1; // 标记为障碍物，不能走 } } // 起点(0,0)路径数初始化为1：自己到自己只有1种走法 arr[0][0] = 1; // 遍历棋盘每一个坐标点 q行 w列 for(int q=0;q<=a;q++){ for(int w=0;w<=b;w++){ // 如果当前点是障碍物，直接跳过，不计算路径 if(grr[q][w]){ continue; } // 路径递推：只能从 上方 或 左方 走过来 // 如果不是第一行，可以从上面(q-1,w)走下来 if(q>0){ arr[q][w] += arr[q-1][w]; } // 如果不是第一列，可以从左边(q,w-1)走过来 if(w>0){ arr[q][w] += arr[q][w-1]; } } } // 输出从(0,0)走到终点(a,b)的总路径数 printf("%d",arr[a][b]); return 0; }