Last active
February 22, 2019 01:43
-
-
Save tristan2077/5257b2459ebe4603eb233995cfde8468 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| package main | |
| import ( | |
| "fmt" | |
| "strconv" | |
| ) | |
| type Position struct{ | |
| X int | |
| Y int | |
| } | |
| type Node struct { | |
| p Position | |
| father Position | |
| } | |
| func canJump(position Position,c_map *[10][9]int) bool{ | |
| if position.X >= 0 && position.Y>=0 && position.X <= 9 && position.Y <= 8 && c_map[position.X][position.Y] == 0 { | |
| return true | |
| }else { | |
| return false | |
| } | |
| } | |
| func findHorseNextJump(p Position, c_map *[10][9]int) (nextPositions []Position){ | |
| // 查看马的8个方向移动是否可行 | |
| nextPositions = []Position{} | |
| p1 := Position{p.X + 1, p.Y + 2} | |
| if canJump(p1,c_map){ | |
| nextPositions = append(nextPositions, p1) | |
| } | |
| p2 := Position{p.X + 1, p.Y - 2} | |
| if canJump(p2,c_map){ | |
| nextPositions = append(nextPositions, p2) | |
| } | |
| p3 := Position{p.X + 2, p.Y + 1} | |
| if canJump(p3,c_map){ | |
| nextPositions = append(nextPositions, p3) | |
| } | |
| p4 := Position{p.X + 2, p.Y - 1} | |
| if canJump(p4,c_map){ | |
| nextPositions = append(nextPositions, p4) | |
| } | |
| p5 := Position{p.X - 1, p.Y + 2} | |
| if canJump(p5,c_map){ | |
| nextPositions = append(nextPositions, p5) | |
| } | |
| p6 := Position{p.X - 1, p.Y - 2} | |
| if canJump(p6,c_map){ | |
| nextPositions = append(nextPositions, p6) | |
| } | |
| p7 := Position{p.X - 2, p.Y + 1} | |
| if canJump(p7,c_map){ | |
| nextPositions = append(nextPositions, p7) | |
| } | |
| p8 := Position{p.X - 2, p.Y - 1} | |
| if canJump(p8,c_map){ | |
| nextPositions = append(nextPositions, p8) | |
| } | |
| return | |
| } | |
| func main(){ | |
| //初始化象棋棋盘 | |
| cheseMap := [10][9]int{} | |
| //初始化马的位置 | |
| horsePosition := Position{0,0} | |
| //初始化目标位置 | |
| targetPosition := Position{0,1} | |
| //存放马节点的队列 用来做广度优先搜索 | |
| horseQueue := []Node{} | |
| horseQueue = append(horseQueue,Node{horsePosition,Position{-1,-1}}) | |
| // map 存放节点 和父亲节点信息 | |
| fatherMap := map[string]Node{} | |
| found := false | |
| lastNode := Node{} | |
| for !found { | |
| //通过切片实现队列 | |
| new_node := horseQueue[0] | |
| new_p := new_node.p | |
| horseQueue = horseQueue[1:] | |
| //标记当前位置已经搜索 | |
| cheseMap[new_p.X][new_p.Y] = 1 | |
| //记录当前节点和其父节点 方便之后找到节点后找出路径 | |
| key := strconv.Itoa(new_p.X) + ":" + strconv.Itoa(new_p.Y) | |
| fatherMap[key] = new_node | |
| if new_p.X == targetPosition.X && new_p.Y == targetPosition.Y{ | |
| fmt.Printf("path %v", new_p) | |
| lastNode = new_node | |
| found = true | |
| }else{ | |
| child := findHorseNextJump(new_p, &cheseMap) | |
| for _,p := range child{ | |
| horseQueue = append(horseQueue,Node{p,new_p}) | |
| } | |
| } | |
| } | |
| for lastNode.father.X != -1 && lastNode.father.Y!=-1{ | |
| key := strconv.Itoa(lastNode.father.X) + ":" + strconv.Itoa(lastNode.father.Y) | |
| lastNode = fatherMap[key] | |
| fmt.Printf("<- %v",lastNode.p) | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment