作者JIWP (神楽めあ的錢包)
看板Marginalman
標題Re: [閒聊] 每日leetcode
時間Mon Nov 25 21:26:58 2024
773. Sliding Puzzle
思路:
就用BFS+hash table
step表示現在的步數
用一個queue紀錄目前有的排序
把queue裡面的排序pop出來，並且將0往其他方向移動
移動後如果得到題目要的排序{{1,2,3},{4,5,0}}就回傳step
不然就把移動後的排序push到queue
如果queue裡面沒東西還是得不到題目要的排序
就回傳-1
golang code :
type PuzzleRecord struct {
puzzle [6]int
location [2]int
}
func slidingPuzzle(board [][]int) int {
zero_point, direction, board_1D, rec := [2]int{}, [][2]int{{1, 0}, {0, 1}, {-
1, 0}, {0, -1}}, [6]int{}, make(map[[6]int]bool)
queue, step, rec := make([]PuzzleRecord, 1), 1, make(map[[6]int]bool)
for i := 0; i < 2; i++ {
for j := 0; j < 3; j++ {
if board[i][j] == 0 {
zero_point[0] = i
zero_point[1] = j
}
board_1D[i*3+j] = board[i][j]
}
}
if board_1D == [6]int{1, 2, 3, 4, 5, 0} {
return 0
}
rec[board_1D] = true
queue[0] = PuzzleRecord{board_1D, zero_point}
for len(queue) > 0 {
cnt := len(queue)
for cnt > 0 {
node := queue[0]
queue = queue[1:]
for i := 0; i < 4; i++ {
x, y := node.location[0]+direction[i][0], node.location[1]+direction[i][1]
tmp := node.puzzle
if x > -1 && y > -1 && x < 2 && y < 3 {
tmp[node.location[0]*3+node.location[1]], tmp[x*3+y] = tmp[x*3+y], tmp[
node.location[0]*3+node.location[1]]
if tmp == [6]int{1, 2, 3, 4, 5, 0} {
return step
}
if !rec[tmp] {
rec[tmp] = true
queue = append(queue, PuzzleRecord{tmp, [2]int{x, y}})
}
}
}
cnt--
}
step++
}
return -1
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.144.16 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Marginalman/M.1732541220.A.B6E.html