这是一个棋牌游戏公司的面试题，也许你也会遇到，看看吧！
/**
*面试题
骑士营救公主
骑士只能向右或者向下移动，遇到陷阱就死了，求骑士营救公主的所有路线，用你熟悉的语言编写程序。 本题由于只能向下和向右，所有他们的路径长度都相同（每个格子长度相等）
解题：寻路， 最短路径，找出所有路径-
*/
如图：
文章图片
对应二维数组关系如图：
文章图片
程序源代码：
struct {
int x;
//路径X轴坐标
int y;
//路径Y轴坐标
int dir;
//路径方向
}stack[120],path[120];
void goMG()
{
int row =8;
//行数
int col =10;
//列数
int maxSize =120;
//栈最多元素个数
int mg[10][12]={//一个迷宫，其四周要加上均为1的外框
{1,1,1,1,1,1,1,1,1,1,1,1},
{1,0,0,0,0,0,0,0,0,1,0,1},
{1,0,0,0,0,1,0,0,0,0,0,1},
{1,0,0,1,0,0,0,0,1,0,0,1},
{1,0,0,0,0,0,0,1,0,0,0,1},
{1,0,0,0,0,0,0,0,0,1,0,1},
{1,0,1,0,0,0,1,0,0,0,0,1},
{1,0,0,0,1,0,0,0,1,0,0,1},
{1,0,1,0,0,0,0,0,0,0,0,1},
{1,1,1,1,1,1,1,1,1,1,1,1}
};
int top = -1;
///栈顶指针
int dir = -1;
//方向 0向右走，1向下走，只能向右或者向下走
int i ,j,find;
int count =0;
//统计找到的路线，路径数计数
int minSize = maxSize;
//最短路径长度
mg[1][1] = -1;
//初始结点进栈
top++;
stack[top].x =1;
stack[top].y=1;
stack[top].dir=-1;
while (top > -1) {//栈不空时循环
i = stack[top].x;
j =stack[top].y;
dir =stack[top].dir;
if(i == row && j == col){//找到了出口，输出路径
printf("\n找到了一条路线：%d，长度为：%d \n ", ++count, (top+1));
for(int k =0;
k <= top;
k++){
printf("(%d,%d) ",stack[k].x,stack[k].y);
if((k+1)%5 ==0){printf("\n");
}//输出时每5个结点换一行
}
if((top+1) < minSize){//记录最短路径
minSize = top +1;
for(int min =0;
min <= top;
min++){
path[min] =stack[min];
}
}
mg[stack[top].x][stack[top].y] = 0;
//让该位置变为其他路径的可走结点
//返回上一个节点，继续查找其他的路径
top--;
i =stack[top].x;
j =stack[top].y;
dir =stack[top].dir;
}
find = 0;
while (dir <2 && find ==0) {
dir++;
switch (dir) {
case0:
i =stack[top].x;
j =stack[top].y+1;
break;
//右边
case1:
i =stack[top].x+1;
j =stack[top].y;
break;
//下边
default:
break;
}
if(mg[i][j] ==0)
find =1;
}
if(find ==1){//找到了下一个可走结点
stack[top].dir = dir;
//修改原栈顶元素的dir值
top++;
//下一个可走结点进栈
stack[top].x = i;
stack[top].y = j;
stack[top].dir = -1;
mg[i][j] = -1;
//把当前走的点赋值，标记为已走过，避免重复走到该结点
}else{
mg[stack[top].x][stack[top].y] = 0;
//让该位置变为其他路径的可走结点
top--;
//返回之前节点
}
}
printf("\n所有的路径条数为：%d \n",count);
//本题由于只能向下和向右，所有他们的路径长度都相同
【面试题目|面试题七 C/C++ 骑士营救公主 骑士只能向右或者向下移动，遇到陷阱就死了，求骑士营救公主的所有路线-程序员面试题】printf("最短路径长度为：%d \n",minSize);
printf("最短路径为：\n");
for (int k =0;
k < minSize;
k++) {
printf("(%d,%d)",path[k].x,path[k].y);
}
printf("\n");
}
部分输出结果：
文章图片
欢迎下方留言谈论，或者加入QQ群83459374交流！
推荐阅读
- 数据结构与算法|《程序员》算法擂台（骑士聚会）
- python|Yolo4-Tiny代码解读
- 算法|哈工大算法设计与分析总结
- 算法|JavaScript数据结构与算法 - 哈希表详解
- CSCI 150 Assembly分析
- 《C语言杂俎》|证明堆排序的时间复杂度
- 蓝桥杯|2018第九届蓝桥杯国赛JAVA B组真题解析（带源码及解析）
- 算法与数据结构的碰撞经典汇总|四平方和 剪枝+枚举 【蓝桥真题】（c++）