回 帖 发 新 帖 刷新版面

主题:帮忙解道题?

求代码啊....

第一行两个整数M,N,代表矩形的行数和列数(1<=M<=100,1<=N<=100).
接下来的M行每行N个字符,仅由'.'和'x'组成。
其中'.'表示通路,'x'表示建筑。
每一步只能走上下左右四个方向的任意一个(如果该方向仍在给定地图内)。
第一行的第一个字符代表是北门,最后一行的最后一个字符代表是南门,这两个字符保证是'.'



输出从北门到南门最快要走几步。
如果从北门不能走到南门,输出-1.

Sample Input
4 4
. x x x
. . . x
x x . x
x x . .
Sample Output
6

回复列表 (共6个回复)

沙发

这应该就是一个很典型的宽度优先遍历的例子吧,深度优先也行。

板凳


如果要路径最短,那深度优先遍历不行了。

3 楼

开个数组 stepnum[m][n],每个元素先初始化为最大值
stepnum[r][c] 保存着到第r行c列最少需要的步数

遍历所有路径,但每到一个位置都和stepnum比较一下,如果小于等于的话,这次遍历就舍弃掉

最后从右下角开始,依次在四周找比当前少一步的元素

4 楼


依然不懂....

5 楼

那您先讲讲您有什么思路没?对算法了解到什么程度?

6 楼


一开始想 逐步扩散搜索,后来想想又比较困难,

我来回复

您尚未登录,请登录后再回复。点此登录或注册