Implementierung des Golang-Labyrinth-Codes

Golang-Labyrinth-Code-Implementierung

Das Labyrinth-Spiel ist ein sehr klassisches Algorithmusproblem im Bereich der Computerprogrammierung und eignet sich auch gut zum Trainieren von Programmierkenntnissen und algorithmischem Denken. In diesem Artikel wird erläutert, wie der Labyrinthspielcode in der GO-Sprache implementiert wird.

1. Initialisieren Sie die Labyrinthkarte.

Zuerst müssen wir die Labyrinthkarte initialisieren und eine Matrix erstellen, um das Labyrinth darzustellen. Während des Implementierungsprozesses können wir jede Labyrinthzelle als Knoten betrachten und sie als zweidimensionales Array darstellen. Der Wert der Labyrinthzelle kann angeben, ob die aktuelle Position begehbar ist oder nicht.

Wir können die Wände des Labyrinths als 0 und den beweglichen Raum als 1 darstellen. Setzen Sie beim Initialisieren der Labyrinthkarte alle Anfangsgitter auf 0. Setzen Sie das Gitter am Rand des Labyrinths auf 0, was bedeutet, dass Sie nicht gehen können. Durch die Festlegung des Randes des Labyrinths können wir Randknoten bei der Suche nach Lösungen bequemer handhaben.

Das Folgende ist die Code-Implementierung:

type point struct{x, y int}

func (p point)add(other point)point {
    return point{p.x + other.x, p.y + other.y}
}

var directions = [4]point{
    {-1, 0}, {0, -1}, {1, 0}, {0, 1},
}

func (g Grid)at(p point) gridValue {
    if p.x < 0 || p.x >= g.width {
        return wall
    }
    if p.y < 0 || p.y >= g.height {
        return wall
    }
    return g.cells[p.y][p.x]
}

func (g Grid)set(p point, v gridValue) {
    g.cells[p.y][p.x] = v
}

type Grid struct {
    width, height int
    cells         [][]gridValue
}

type gridValue byte

const (
    empty gridValue = iota
    wall
    start
    end
    path
)

func newGrid(width, height int) Grid {
    cells := make([][]gridValue, height)
    for i := range cells {
        cells[i] = make([]gridValue, width)
        for j := range cells[i] {
            cells[i][j] = empty
        }
    }
    return Grid{width: width, height: height, cells: cells}
}

2. Aus dem Labyrinth herauskommen

Wir können den Tiefensuchalgorithmus (DFS) verwenden, um vom Startpunkt des Labyrinths bis zum Ende zu gehen und alle Wege zu markieren. Der DFS-Algorithmus basiert auf der Stapelmethode, um in eine Richtung weiterzulaufen, bis er einen bestimmten Endpunkt erreicht oder eine Position erreicht, an der er nicht weitergehen kann. Wenn wir eine Position erreichen, an der wir nicht weitermachen können, kehren wir zur vorherigen Position zurück und wiederholen den Vorgang, bis wir den Endpunkt gefunden haben oder alle Pfade durchlaufen wurden.

Das Folgende ist der mit dem DFS-Algorithmus implementierte Code:

func (g Grid)solveDFS() {
    start := g.findStart()
    g.dfsRecursive(start)
}

func (g Grid)findStart() point {
    for y, row := range g.cells {
        for x, value := range row {
            if value == start {
                return point{x, y}
        }
    }
  }
  panic("start point not found")
}

func (g Grid)dfsRecursive(current point) {
    if !g.inBounds(current) || g.at(current) == wall {
        return
    }
    if g.at(current) == end {
        return
    }
    g.set(current, path)
    for _, direction := range directions {
        g.dfsRecursive(current.add(direction))
    }
}

3. Finde den kürzesten Weg im Labyrinth

Obwohl der DFS-Algorithmus alle Wege bis zum Ende finden kann, kann er nicht den kürzesten Weg finden. Um den kürzesten Weg zu finden, müssen wir den Breadth First Search (BFS)-Algorithmus verwenden. Der BFS-Algorithmus ist ein Algorithmus zum Finden des kürzesten Pfades.

Der BFS-Algorithmus basiert auf der Warteschlangenmethode, die vom Startpunkt aus alle Nachbarknoten der aktuellen Warteschlange erweitert, bis sie den Endpunkt erreicht. Wenn wir den Endpunkt gefunden haben, müssen wir in die entgegengesetzte Richtung zurückgehen und den kürzesten Weg markieren.

Das Folgende ist der Code, der mit dem BFS-Algorithmus implementiert wurde:

type node struct {
    point
    distance int
}

func (g Grid)solveBFS() {
    start := g.findStart()
    queue := []node{{point: start}}
    seen := map[point]bool{start: true}
    for len(queue) > 0 {
        current := queue[0]
        queue = queue[1:]
        if g.at(current.point) == end {
            g.markShortestPath(current)
            return
        }
        for _, direction := range directions {
            next := current.add(direction)
            if !g.inBounds(next) || seen[next] || g.at(next) == wall {
                continue
            }
            seen[next] = true
            queue = append(queue, node{point: next, distance: current.distance + 1})
        }
    }
}

func (g Grid)markShortestPath(current node) {
    for ; g.at(current.point) != start; current.distance-- {
        g.set(current.point, path)
        for _, direction := range directions {
            next := current.add(direction)
            if g.at(next) == path && current.distance - 1 == g.at(next).distance {
                current.point = next
                break
            }
        }
    }
}

Im obigen Code definieren wir eine Knotenstruktur, die die Knotenkoordinaten und den Abstand zum Knoten enthält. Im BFS-Algorithmus verwenden wir eine Warteschlange zum Speichern der Knoten, die aktuell durchsucht werden müssen, und verwenden eine Karte zum Aufzeichnen der besuchten Knoten, um wiederholte Suchvorgänge zu vermeiden. Während des Suchvorgangs zeichnen wir die Entfernung jedes Knotens zum Startpunkt auf, bis der Endpunkt gefunden ist. Anschließend gehen wir zurück und überqueren den kürzesten Weg und kennzeichnen den Weg als Pfad.

Das obige ist der detaillierte Inhalt vonImplementierung des Golang-Labyrinth-Codes. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!