本文主要是介绍华为优招面试题---迷宫问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
昨天参加了华为优招，被问到一道算法题，当时，有点思路，记得不论是在人工智能课还是在算法课上，这些都有讲到过，然后想了好久，回答出来了不是一个最优解的答案。下来总结一下这道题的思路。
题目
有一个迷宫，里面有障碍物，最左上角是入口，右下角是出口，请找出一条路径可以走出迷宫。大致就像下面这个图（阴影部分表示有障碍物）：
如何找到一条从入口通往出口的路径？
思路
当时的想法：按照我们走迷宫的思路一样，判断当前位置的可走的方向有一个还是多个，如果有一个方向可走，那没有别的选择，前进；如果有多个方向可走，就先选一条去走，并把这个位置设一个标记；如果各个方向不可走回退，退到最近的设了标记的位置上。这样一次次循环就可以找到一条路径。
接着面试官问，这个想法这样想很简单，那有没有想过如何去实现？（数据结构这些如何去设计）
我回答可以用树来表示，像下面这样：
有路径就扩展树节点；没有路径就表示该节点不能再扩展，也就是没有路可走的情况。如果沿着树去遍历，扩展到了一个没有子孩子的节点时，就需要再回溯，回溯到上一个有标记的节点，继续其他分支的扩展。这种应该算是树的深度优先遍历，但这样是不能找到最优路径的，有可能找出来的是最长的。如何去找最优路径没有回答上来，面试官提了一下，可以用广度优先遍历（BFS）来做，这样得到的应该就是最短路径。
总结
这次面试在算法和数据结构上还是比较欠缺，所以不管什么语言，不管什么岗位，对于算法和数据结构还是要求要掌握的，所以下来也需在这方面努力！加油！希望找到满意的工作！
这篇关于华为优招面试题---迷宫问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
