马拦过河卒 时间限制:10000MS  内存限制:65536KTotal Submit:9 Accepted:3 问题描述 棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳 跃一步可达的点称为对方马的控制点。因此称之为“马拦过河卒”。 　　棋盘用坐标表示，A点(0, 0)、B点(n, m)(n, m为不超过15的整数)，同样马的位置坐标是需要给出的。现在要求你计算出卒从A点能够到达 B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。 输入 一行四个数据，分别表示B点坐标和马的坐标。（保证所有的数据有解） 输出 一个数据，表示所有的路径条数。 输入样例 6 6 3 3 输出样例 6 题目来源 // MY CODE (注意卒不能通过马所在的位置，象棋里是可以的) #include <stdio.h> struct node{ int  right; int  down; int  x,y;}stack[40]; struct horse{ int x,y;}horse[8]; int test(int x,int y,struct horse *h,int k){ int i; for(i = 0; i < k; i++)  if(h[i].x == x && h[i].y == y)   return 1; return 0;} int main(){ int  xd,yd,xh,yh,i,k,m; int  b[] = {-2,-1,1,2,2,1,-1,-2}; int  c[] = {1,2,2,1,-1,-2,-2,-1};  while(scanf("%d%d%d%d",&xd,&yd,&xh,&yh)!=EOF){  for(k = i = 0; i < 8; i++){   if(xh+c[i]<0 || xh+c[i]>xd || yh+b[i]<0 || yh+b[i]>yd)    continue;   horse[k].x = xh + c[i];   horse[k].y = yh + b[i];   k++;  }  stack[0].x=stack[0].y=stack[0].down=stack[0].right=0;  for(m = i = 0; i >= 0;){   if(stack[i].x == xd && stack[i].y == yd){    i--;    m++;   }   if(stack[i].down == 0){    stack[i+1].y = stack[i].y + 1;    stack[i+1].x = stack[i].x;    stack[i].down = 1;    i++;    stack[i].down = stack[i].right = 0;   }   else if(stack[i].right == 0){    stack[i+1].x = stack[i].x + 1;    stack[i+1].y = stack[i].y;    stack[i].right = 1;    i++;    stack[i].down = stack[i].right = 0;   }   else{    i--;    continue;   }   if( stack[i].x > xd || stack[i].y > yd  ||    test(stack[i].x,stack[i].y,horse,k) ||    (stack[i].x == xh && stack[i].y == yh) ){    i--;    continue;   }  }  printf("%d\n",m); } return 0;} 更好的处理方法：    用一个二维数组表示棋盘，将该二维数组全部初始化为 0将马的位置以及马能够踏到的地方设为1，为避免边界的计算测试可以在棋盘的右边和下边增加一层外围 1。 

评论