本文主要是介绍骑马走江湖，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
江湖是什么，对于在象棋界厮杀的蒜头君来说，江湖就是一个矩阵，他的目标，就是在江湖之中骑着马，从他的位置出发，走到终点。
当然，蒜头君的马也遵从中国象棋中的“马走日”的规则，而且在矩阵中，也会有一些障碍物，马不能跳到障碍物上；如果蒜头君的马面前有障碍物，即被“别马腿”，那么他将不能跳向有障碍物的左前和右前这两个方向。
请问最少需要多少步，蒜头君才能骑着马跳到终点。
输入格式
第一行输入两个数 nn 和 mm，代表矩阵的行数和列数，2 \leq n \leq m < 1002≤n≤m<100。
接下来输入 nn 行字符串，其中s代表起点，e代表终点，.代表空地，#代表障碍物。
输出格式
输出一个整数，表示骑马跳到终点的最小步数。如果跳不到终点，输出 -1−1。
#include <stdio.h>
#include <stdlib.h>int length,width;///地图规模
char maze_map[101][101];
int dis[101][101];
int flag;
int visited[101][101];///标记初始为0，表示未走过typedef struct Point
{int x;int y;
} Point;typedef struct Queue
{Point *step;int step_length,head,tail;
} Queue;void queue_init(Queue *q,int length_inpu)
{q->step=(Point *)malloc(sizeof(Point)*length_inpu);q->step_length=length_inpu;q->head=0;q->tail=-1;
}void queue_push(Queue *q,Point in_point)
{if(q->tail+1<q->step_length){q->tail++;q->step[q->tail]=in_point;}
}void queue_pop(Queue *q)
{q->head++;
}Point queue_front(Queue *q)
{return q->step[q->head];
}int queue_empty(Queue *q)
{if(q->head>q->tail){return 1;}else{return 0;}
}void queue_clear(Queue *q)
{free(q->step);free(q);
}int can(int x,int y)///判断能不能走能返回1不能返回0
{///判断是否超界、是否走过、是否为路if((x>=0 && x<length) && (y>=0 && y<width) && maze_map[x][y]!='#' && visited[x][y]==0){return (1);}else{return (0);}
}int find_path(Queue *q,Point in_start_point,Point in_end_point)
{queue_push(q,in_start_point);while(!queue_empty(q)){Point current_point=queue_front(q);queue_pop(q);if(current_point.x==in_end_point.x && current_point.y==in_end_point.y){if(dis[in_end_point.x][in_end_point.y]==0){break;}printf("%d\n",dis[in_end_point.x][in_end_point.y]);flag = 1;break;}int dx[]= {-1,1,2,2,1,-1,-2,-2};int dy[]= {2,2,1,-1,-2,-2,-1,1};for(int i=0; i<8; i++){/// 偏移量 上一个点的xint nx=dx[i]+current_point.x;int ny=dy[i]+current_point.y;int bx = current_point.x + dx[i]/2;int by = current_point.y + dy[i]/2;if(maze_map[bx][by]=='#'){//别马腿continue;}if(can(nx,ny)){dis[nx][ny]=dis[current_point.x][current_point.y]+1;//关键///入队Point tmp;tmp.x=nx;tmp.y=ny;visited[nx][ny]=1;queue_push(q,tmp);///从当前元素的后面增加元素}}}if(flag==0){//无法走到终点的情况printf("-1\n");}
}void output_map(char maze_map[21][21])
{for(int i=0; i<length; i++){for(int j=0; j<width; j++){printf("%c",maze_map[i][j]);}printf("\n");}
}int main()
{Point start_point,end_point;Queue *queue=(Queue *)malloc(sizeof(Queue));//memset(maze_map,'.',sizeof(maze_map));scanf("%d %d",&length,&width);queue_init(queue,length*width);for(int i=0; i<length; i++){scanf("%s",maze_map[i]);for(int j=0; j<width; j++){if(maze_map[i][j]=='s'){start_point.x=i;start_point.y=j;}if(maze_map[i][j]=='e'){end_point.x=i;end_point.y=j;}}}find_path(queue,start_point,end_point);//output_map(maze_map,length,width);
}
这篇关于骑马走江湖的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
