马拦过河卒

时间限制:10000MS  内存限制:65536K
Total 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。
 

评论