写给妹妹的编程札记 4

札记 4"/>

写给妹妹的编程札记 4

        《写给妹妹的编程札记 3 - 穷举: 深度优先搜索/广度优先搜索》中， 我们了解到基本的深度优先搜索和广度优先搜索。 来点实战吧， 使用搜索技术来解决一些实际的问题。 

        首先来看看怎么使用深度优先搜索解决迷宫问题？

        假设，输入的迷宫如下列数据表示： 

                第一行包含两个整数，分别表示行数 - r 和列数 - c

                从第二行开始，包括r行， 每行c个字符。 “#”表示墙壁，不能通过； “.”表示空位，可以通过

        我们需要解决的问题是，寻找从[0][0]这个位置，走到[r-1][c-1]这个位置的最短路径。

3 4
...#
.#.#
....
6 8
.#######
.......#
.##.##.#
....#.##
#.######
#.......

        《写给妹妹的编程札记 3 - 穷举: 深度优先搜索/广度优先搜索》中讨论的是树的遍历ÿ