课程设计——中国象棋中的跳马问题

<wbr>中国象棋中的跳马问题</wbr>

题目描述

现在棋盘的大小不一定，由p，q给出，并且在棋盘中将出现障碍物（限制马的行动，与象棋走法相同）

输入

第一行输入n表示有n组测试数据。

每组测试数据第一行输入2个整数p,q，表示棋盘的大小(1<=p,q<=100)。
每组测试数据第二行输入4个整数，表示马的起点位置与终点位置。(位置的取值范围同p,q)
第三行输入m表示图中有多少障碍。
接着跟着m行，表示障碍的坐标。

输出

马从起点走到终点所需的最小步数。
如果马走不到终点，则输入“can not reach!”

样例输入

2 9 10 1 1 2 3 0 9 10 1 1 2 3 8 1 2 2 2 3 3 3 4 1 4 3 2 2 4 13

样例输出

1 can not reach!

提示

<wbr></wbr>

此题是一个搜索题，可用DFS或BFS，建议选择BFS(广搜)。一开始把马的起始点加入队列，然后用广搜的思想把此点能到达的其他点加入队列，这里需要一个数组用来记录此点在之前是否已经加入队列，如果加入过队列当中，就不需要再加入了，直到队列里的元素为空，或者搜索到了终点，搜索即停止，然后输出相应答案即可。
参考代码如下：

#include<stdio.h>
#define MAX 150
#define SIZE 10201
#define OK 1
//马下一步最多能跳的地方的个数
#define  M  8
//马可能跳的位置的相对横纵坐标,上、右、下、左 
int Movex[M] = {-1,1,  2, 2,   1,-1,  -2,-2};
int Movey[M] = { 2,2,  1,-1,  -2,-2,  -1,1};

//马跳的时候最多遇到的障碍数
#define  B  4
//马的障碍的位置的相对总横坐标，上、右、下、左
int Barx[B] = {0,1,0,-1};
int Bary[B] = {1,0,-1,0};

typedef struct 
{
    int step;//记录步数
int flag;//标记
}Chessboard;//棋盘类型

typedef struct
{
int lnum;
int rnum;//记录元素下标
}Queue;//队列类型

Queue queue[SIZE];//队列
int rear,front;//队列指针
Chessboard board[MAX][MAX];

int a,b,c,d,row,line;//起点，终点坐标以及行列值


int BFS()
{
    int x0,y0;
int mx,my,bx,by;
int i;
rear=-1;
front=-1;//队列指针初始化
board[a][b].step=0;//起点的步数记为0
board[a][b].flag=1;//起点标记已经进过队列
    rear++;
queue[rear].lnum=a;
queue[rear].rnum=b;//起点先进队列
while(front!=rear)//队列不为空
{
        front++;
x0=queue[front].lnum;
y0=queue[front].rnum;//出队列
if(x0==c && y0==d)  return OK;//找到了终点就停止搜索
for(i=0;i<M;i++)//m=8,共有八个地方可以跳
{
          //算出值，利用该值来判断向该方向跳是否有障碍物阻碍
bx = x0+Barx[i/2];
by = y0+Bary[i/2];//用来判断是否有障碍物
//算出值，利用该值来判断向该方向上日字的端点处是否有障碍物或已走过
//即下一位置的坐标
mx = x0 + Movex[i];
my = y0 + Movey[i];
if(board[bx][by].flag!=-1)
{
                if(mx>0&&mx<=row && my>0&&my<=line && !board[mx][my].flag)//不能越界，board[mx][my].flag必为0
{
rear++;
                    queue[rear].lnum=mx;
                    queue[rear].rnum=my;//进队列  
board[mx][my].flag=1;//标记为已经走过
board[mx][my].step=board[x0][y0].step+1;//路径值是其根部的路径值加1
}//if
}//if
}//for
}//while
 return 0;
}


int main()
{
int n,m,e,f;
int k,i,j;
scanf("%d",&n);//一共n组测试数据
for(k=0;k<n;k++)
{
scanf("%d %d",&row,&line);//输入棋盘大小 行列
      for(i=1;i<=row;i++)
for(j=1;j<=line;j++)
board[i][j].flag=0;//初始化，全部标记为0
 scanf("%d %d %d %d",&a,&b,&c,&d);//输入起点终点坐标值
   scanf("%d",&m);//m个障碍
      for(i=0;i<m;i++)
  {
   scanf("%d %d",&e,&f);
   board[e][f].flag=-1;//障碍点标记为-1
  }
 if(BFS())
      printf("%d\n",board[c][d].step);
      else  printf("can not reach!\n");
}
return 0;
}