障害物のあるグリッドの最短経路

前置き

Cracking the Coding Interviewの8.2に以下のような問題がありました。

世界で闘うプログラミング力を鍛える本 コーディング面接189問とその解法

問題: グリッド状を動くロボット

r行とc列のグリッド状の左上にロボットが座っています。ロボットは右と下の2つの方向にしか進むことができません。ロボットが通ることのできない「立ち入り禁止」のセルがあるとした場合、左上の地点から右下の地点まで移動する道順を見つけるアルゴリズムを設計してください。

この問題の解法として、スタートからゴールまでたどり着く、どれか一つのパスを見つけるアルゴリズムが紹介されていました。 しかし、どうせなら全てのパスを見つける方が一般的だろうと思い実装してみました。

アルゴリズム

(c, r)にたどり着くことを考えたとき、基本的には(c, r-1)もしくは(c-1, r)から遷移する2通りがあります。つまり、(c, r)への経路は、(c, r-1)までの経路に"↓"方向を1つ加えたものと、(c-1, r)までの経路に"→"方向を1つ加えたものをマージしたものになります。しかし、この問題には障害物があるため、正確には2通り以下となります。

以上の遷移を持つ動的計画法を用いることで(0, 0)から(c, r) (実際には(c-1, r-1))までの全ての経路を (文字列連結の時間を無視した場合)で求めることができます。

コード

言語はGoです。

package main

import (
    "fmt"
    "strings"
)

type point struct {
    x int
    y int
}

var dp map[point][]string
var locked map[point]bool

func appendToAll(bases []string, as string) []string {
    strs := make([]string, 0)
    for _, base := range bases {
        // lockedが含まれていたら更新しない&&含まない
        if !strings.Contains(base, "[locked]") {
            strs = append(strs, base+as)
        }
    }
    return strs
}

func solve(p point, routes []string) []string {
    if val, ok := dp[p]; ok {
        return val
    }

    x := p.x
    y := p.y
    dx := point{x - 1, y}
    dy := point{x, y - 1}

    if locked[dx] && locked[dy] {
        rts := appendToAll(routes, "[locked]")
        dp[p] = rts
        return dp[p]
    } else if locked[dy] {
        rtsdx := solve(dx, routes)
        rtsX := appendToAll(rtsdx, "→")
        rtsY := appendToAll(rtsdx, "[locked]")
        dp[p] = append(rtsX, rtsY...)
        return dp[p]
    } else if locked[dx] {
        rtsdy := solve(dy, routes)
        rtsX := appendToAll(rtsdy, "[locked]")
        rtsY := appendToAll(rtsdy, "↓")
        dp[p] = append(rtsX, rtsY...)
        return dp[p]
    }

    rtsdx := solve(dx, routes)
    rtsX := appendToAll(rtsdx, "→")
    rtsdy := solve(dy, routes)
    rtsY := appendToAll(rtsdy, "↓")
    dp[p] = append(rtsX, rtsY...)
    return dp[p]
}

func main() {
    var r, c int
    fmt.Scan(&r, &c)

    var k int
    fmt.Scan(&k)
    locked = make(map[point]bool, k)
    for i := 0; i < k; i++ {
        var lx, ly int
        fmt.Scan(&lx, &ly)
        locked[point{lx, ly}] = true
    }
    // 枠外もlockedに加える
    for i := 0; i < c; i++ {
        locked[point{-1, i}] = true
    }
    for i := 0; i < r; i++ {
        locked[point{i, -1}] = true
    }

    dp = make(map[point][]string)
    dp[point{0, 0}] = make([]string, 1)
    routes := solve(point{c - 1, r - 1}, make([]string, 1))
    for _, route := range routes {
        fmt.Println(route)
    }
}

実行例

入力

3 3 1 1 0

出力

↓↓→→

↓→↓→

↓→→↓

コメント

• 障害物のある場所をlockedというmapを使うことで管理しています
• 枠外(x<0, y<0)もlockedに加えることで場合分けを避けました
• appendToAllの際に、[locked]が含まれている経路は無視することで障害物を通るパスは除かれています
• solveが少し冗長な気がしますが、無駄に再帰的に呼ばれないようにするとこの書き方しか思いつきませんでした…
• 幅優先探索でも解ける気がします