G-Man网格寻路Go代码输出异常：预期155却得到90

问题背景 #

G-Man是一款在6×6网格中移动的游戏，需操控G-Man从起点到终点，选择功耗最低的路径：

• 位置表示：用x,y坐标+朝向（N/E/S/W）表示，例如2,1 E代表x=2、y=1，朝向东方。
• 功耗规则：初始功耗200，每次90度转向消耗5点，每移动1格消耗10点。
• 目标：计算到达终点后的剩余功耗，必须走最短路径且转向次数最少。

问题详情 #

输入内容：

SOURCE 2 1 E
DESTINATION 4 3

预期输出：POWER 155
但运行下方Go代码后，实际输出为90，需排查代码问题。

main.go #

package main

import (
    "bufio"
    "fmt"
    "os"
    "strings"
)

var Source []string
var Destination []string

const (
    gridSize  = 6
    maxPower  = 200
    movePower = 10
    turnPower = 5
)

func main() {
    cliArgs := os.Args[1:]

    if len(cliArgs) == 0 {
        fmt.Println("Please provide the input file path")

        return
    }

    filePath := cliArgs[0]
    file, err := os.Open(filePath)

    if err != nil {
        fmt.Println("Error opening the input file")

        return
    }

    defer file.Close()
    scanner := bufio.NewScanner(file)

    for scanner.Scan() {

        args := scanner.Text()
        argList := strings.Fields(args)

        designation := argList[0]
        coordinates := argList[1:]

        if designation == "SOURCE" {
            Source = coordinates
        }
        if designation == "DESTINATION" {
            Destination = coordinates
        }
    }

    RemainingPower := solveForShortestPath(Source, Destination)
    fmt.Printf("POWER %d", RemainingPower)
}

PriorityQueue.go #

package main

type Cell struct {
    X, Y      int
    Power     int
    Direction string
}

type PriorityQueue []*Cell

func (pq PriorityQueue) Len() int {
    return len(pq)
}

func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].Power < pq[j].Power
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
    item := x.(*Cell)
    *pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    *pq = old[0 : n-1]
    return item
}

solveForShortestPath.go #

package main

import (
    "container/heap"
    "strconv"
)

func solveForShortestPath(Source, Destination []string) int {
    sourceX, _ := strconv.Atoi(Source[0])
    sourceY, _ := strconv.Atoi(Source[1])

    destX, _ := strconv.Atoi(Destination[0])
    destY, _ := strconv.Atoi(Destination[1])

    visited := make([][]bool, gridSize)
    for i := range visited {
        visited[i] = make([]bool, gridSize)
    }

    pq := make(PriorityQueue, 0)
    heap.Init(&pq)

    sourceCell := &Cell{X: sourceX, Y: sourceY, Power: maxPower, Direction: Source[2]}
    heap.Push(&pq, sourceCell)
    visited[sourceX][sourceY] = true

    for len(pq) > 0 {
        currentCell := heap.Pop(&pq).(*Cell)

        row := currentCell.X
        col := currentCell.Y
        dir := currentCell.Direction

        if row == destX && col == destY {
            return currentCell.Power
        }

        delRow := []int{-1, 0, +1, 0}
        delCol := []int{0, +1, 0, -1}
        for i := 0; i < 4; i++ {
            newRow := row + delRow[i]
            newCol := col + delCol[i]

            if newRow >= 0 && newRow < gridSize && newCol >= 0 && newCol < gridSize && !visited[newRow][newCol] {
                newPower := currentCell.Power
                newDirection := getNewDirection(dir, delRow[i], delCol[i])
                if newDirection != dir {
                    newPower -= turnPower
                }
                newPower -= movePower
                if newPower >= 0 {
                    visited[newRow][newCol] = true
                    heap.Push(&pq, &Cell{X: newRow, Y: newCol, Power: newPower, Direction: dir})
                }
            }
        }
    }

    return -1
}

getNewDirection.go #

package main

func getNewDirection(currentDirection string, delRow int, delCol int) string {
    if currentDirection == "E" && delRow == 0 {
        return "E"
    } else if currentDirection == "E" && delRow == -1 {
        return "N"
    } else if currentDirection == "E" && delRow == +1 {
        return "S"
    } else if currentDirection == "S" && delCol == 0 {
        return "S"
    } else if currentDirection == "S" && delCol == -1 {
        return "W"
    } else if currentDirection == "S" && delCol == 1 {
        return "E"
    } else if currentDirection == "W" && delRow == -1 {
        return "N"
    } else if currentDirection == "W" && delRow == 0 {
        return "W"
    } else if currentDirection == "W" && delRow == 1 {
        return "S"
    } else if currentDirection == "N" && delCol == 0 {
        return "N"
    } else if currentDirection == "N" && delCol == 1 {
        return "E"
    }
    return "W"
}

代码问题排查点 #

1. 优先级队列排序逻辑错误：当前Less方法以pq[i].Power < pq[j].Power排序，会让功耗越低的单元格优先级越高。但我们需要优先选择剩余功耗高（消耗少）的路径，应改为return pq[i].Power > pq[j].Power。
2. 访问标记逻辑错误：当前仅用二维数组标记坐标是否访问过，但同一坐标可能有不同朝向和剩余功耗的状态，直接标记会忽略更优路径。需改为三维数组visited[x][y][direction]，或记录每个坐标的最优剩余功耗，仅当新路径剩余功耗更高时才更新。
3. 新单元格方向设置错误：推入新单元格时使用Direction: dir（当前方向），但实际应设置为计算出的newDirection，否则后续转向计算会出错。
4. getNewDirection函数逻辑缺失：未处理N朝向向左（delCol=-1）的情况，会默认返回W，需补充：else if currentDirection == "N" && delCol == -1 { return "W" }。
5. 最短路径保证缺失：当前优先队列未优先保证最短路径（移动步数最少），需将优先级改为“步数优先，其次剩余功耗”，或用BFS结合优先级，确保先处理步数少的路径，再在同步数下选功耗最低的。

按预期输入计算：起点(2,1)朝E到终点(4,3)，最短路径需移动4格、转向1次，总消耗为1*5 +4*10=45，剩余200-45=155，与预期一致。当前代码因上述错误计算出了错误的路径消耗。

内容的提问来源于stack exchange，提问作者SHUBHAM