课程设计——中国象棋中的跳马问题
现在棋盘的大小不一定，由p，q给出，并且在棋盘中将出现障碍物（限制马的行动，与象棋走法相同）
第一行输入n表示有n组测试数据。
每组测试数据第一行输入2个整数p,q，表示棋盘的大小(1<=p,q<=100)。
每组测试数据第二行输入4个整数，表示马的起点位置与终点位置。(位置的取值范围同p,q)
第三行输入m表示图中有多少障碍。
接着跟着m行，表示障碍的坐标。
马从起点走到终点所需的最小步数。
如果马走不到终点，则输入“can not reach!”
此题是一个搜索题，可用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;//起点的步数记为0board[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;}