上回分析到了炸弹的数量与位置问题，得出了随机位置的最多炸弹数量，但炸弹数量看起来并不多，这使得路径十分随意，因此，炸弹数量我不想太少，直接自己手动定义了。其实还有个思路的，就是按照区域随机分配炸弹，比如每个5×5区域就随机分配一个炸弹，实现方式还有其他形式，不在这个问题上纠结了。我今天想实现一个功能，自动打印出从起点到终点的最短路径，以便在炸弹数量足够多的时候，很快得出一个答案。

一个m×n的地图，我们很容易知道最短路径是m+n-1。不过炸弹的设定，让这个最短路径发生了变化，炸弹的周围不能经过，所以可能出现以下这种情况：

min-path.png

这是炸弹足够多的时候会出现的情况，如果是炸弹比较少的话，其实并不会干扰到我们，我们很容易就可以走出一个最短路径，因为经过平移，我们知道，只要我们只要不往上不往左走，就是一条最短路径了。

但是炸弹足够多的话，就不能这么定义了，这干扰了我们的路径。我们前进的每一步可能是任意的三个方向，同时，最短路径可能有多条。当前我们在一个点上，要思考下个点走到哪去。我们到下个点也一样要做同样的思考。这就很明显是个递归的问题了。明白是个递归问题，我们就可以定义我们的路径是怎么走：

        pointR, isStopR := components.NewPoint(rp, point, "right")        pointD, isStopD := components.NewPoint(rp, point, "down")                pointL, isStopL := components.NewPoint(rp, point, "left")                pointU, isStopU := components.NewPoint(rp, point, "up")

每个点理论上都可能会有四个方向可以走，但为什么我前面说了是“三个”？因为有一个方向是你刚走过来的，比如你上个点是从右边来的，这时你再回到右边，那就走了回头路，这是没有意义的。

递归有时候是个解决问题的利器，但是比较难的点是让它停下来。我们要思考一下它的终止条件。

1. 就是刚刚的回头路问题，走过的点是不允许回到的，回到了则代表这条路走不通，应该放弃。

func HasDuplicatedPoint(p *Point) bool {    _p := p    x, y := _p.X, _p.Y    for _p.LastPoint != nil {        if _p.LastPoint.X == x && _p.LastPoint.Y == y {            return true        } else {            _p = _p.LastPoint        }    }    return false}

2. 不能经过的点也不是下一步应该去的方向，比如边界、比如炸弹区域，走到了这一步说明此路不通。

    for _, v := range rp.BoomPosition {        if x == v[0] && y == v[1] {            return lastPoint, true        }    }    for _, v := range rp.TrapPosition {        if x == v[0] && y == v[1] {            return lastPoint, true        }    }

3. 到达终点，毫无疑问，这表示我们已经完成任务了。

if rp.EndPoint[0] != point.X || rp.EndPoint[1] != point.Y {       ……}

此时，我们已经具备了得到所有路径的条件，但是有个问题，我要的是最短路径，而递归，会把所有的路径都找出来。这个好办，我用一个map来存所有的路径，并从中找出一个路径最短的。问题至此解决。

有兴趣的话可以去看看代码：https://github.com/TomatoMr/boomboom.git。

欢迎关注我的公众号：onepunchgo，给我留言。

image

给这篇文章的作者打赏

微信扫一扫打赏

支付宝扫一扫打赏

×

打赏 点赞(0)