廣度優(yōu)先搜索
- 問題描述：
- |
[x1]|[x2]|[x3]|[x4]
------|-----|-----|-----|-----
[y1]| 0 | 0 | 1 | 0
[y2]| 0 | 0 | 0 | 0
[y3]| 0 | 0 | 1 | 0
[y4]| 0 | 1 |A| 0
[y5]| 0 | 0 | 0 | 1
上面的表格是一張藏寶圖的抽象，坐標中0表示空地堂鲜，1表示有障礙物晋南， A表示藏寶點，現(xiàn)在我們從坐標(1, 1)出發(fā)開始尋寶之旅戳表。
這里我們用廣度優(yōu)先的思想來思考這個問題柬唯。
type node struct {
x int // x坐標
y int // y坐標
s int // 步數(shù)
}
func BFS() {
fmt.Println("BFS")
var queue []node = make([]node, 50) // 隊列
var head, tail int // 分別標記隊列頭和尾
var treasureMap = [5][4]int{ // 地圖
{0, 0, 1, 0},
{0, 0, 0, 0},
{0, 0, 1, 0},
{0, 1, 0, 0},
{0, 0, 0, 1},
}
var locationMarks [5][4]int // 標記地圖上哪些點已經(jīng)走過
var derections = [4][2]int{ // 4個移動方向
{1, 0}, // 向右
{0, 1}, // 向下
{-1, 0}, // 向左
{0, -1}, // 向上
}
var targetX, targetY int = 2, 3
var flag bool = false
/*--------------------- 開始尋寶 ---------------------------*/
/*------------ 從起點開始 ---------------*/
// 初始化隊列
head = 0
tail = 0
// 標示起點
// 起點入隊 這里我們默認從(X0, Y0)開始
queue[tail].x = 0
queue[tail].y = 0
queue[tail].s = 0
tail++ // 尾指針后移一位
locationMarks[0][0] = 1 // 標記已經(jīng)走過的點
/*------------ 走起 ---------------*/
for head < tail { // 隊列不為空
// 枚舉4個方向
for i := 0; i < len(derections); i++ {
// 計算下一個點坐標
tx := queue[head].x + derections[i][0]
ty := queue[head].y + derections[i][1]
if tx > 3 || tx < 0 || ty > 4 || ty < 0 {
continue
}
// 坐標不是障礙物 并且 沒有標記過
if treasureMap[ty][tx] == 0 && locationMarks[ty][tx] == 0 {
locationMarks[ty][tx] = 1 // 標記已經(jīng)走過
// 將新的坐標入隊
queue[tail].x = tx
queue[tail].y = ty
queue[tail].s = queue[head].s + 1
tail++
}
// 如果已經(jīng)到達藏寶點
if tx == targetX && ty == targetY {
flag = true
break
}
}
if flag {
break
} else {
head++ // 移動頭指針东跪，遍歷下一層
}
}
for i := 0; i < tail; i++ {
fmt.Println(i, " ", queue[i])
}
}
結(jié)果
步驟
