写点什么

[Day45]-[BFS]- 滑动谜题

作者:方勇(gopher)
  • 2022 年 5 月 19 日
  • 本文字数:1133 字

    阅读完需:约 4 分钟

773. 滑动谜题

在一个 2 x 3 的板上(board)有 5 块砖瓦,用数字 1~5 来表示, 以及一块空缺用 0 来表示。一次 移动 定义为选择 0 与一个相邻的数字(上下左右)进行交换.

最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。

给出一个谜板的初始状态 board ,返回最少可以通过多少次移动解开谜板,如果不能解开谜板,则返回 -1 。

 

示例 1:



输入:board = [[1,2,3],[4,0,5]]输出:1解释:交换 0 和 5 ,1 步完成
复制代码

示例 2:



输入:board = [[1,2,3],[5,4,0]]输出:-1解释:没有办法完成谜板
复制代码

示例 3:



输入:board = [[4,1,2],[5,0,3]]输出:5解释:最少完成谜板的最少移动次数是 5 ,一种移动路径:尚未移动: [[4,1,2],[5,0,3]]移动 1 次: [[4,1,2],[0,5,3]]移动 2 次: [[0,1,2],[4,5,3]]移动 3 次: [[1,0,2],[4,5,3]]移动 4 次: [[1,2,0],[4,5,3]]移动 5 次: [[1,2,3],[4,5,0]]
复制代码

题解:

func TestSlidingPuzzle(t *testing.T) {	var board = [][]int{ // 初始化board		{4, 1, 2},		{5, 0, 3},	}
start := func() string { // 将初始化board转换成一维字符串 start := "" for i := 0; i < 2; i++ { for j := 0; j < 3; j++ { start += strconv.Itoa(board[i][j]) } } return start }()
var bfs func() int bfs = func() int { // 广度搜索 var step int // 返回需要的步骤 var target = "123450" // 目标状态 var queue []string // 搜索的字符串 var visited = make(map[string]struct{}) // 剪枝标记已经访问过的数据 var neighbor = [][]int{ // 相邻的索引 {1, 3}, // 0 相邻的索引 1,3 {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}, }
queue = append(queue, start) // 加入到queue中 for len(queue) > 0 { q := queue // 用一个新队列接收,方便重新计数 queue = nil for _, current := range q { // 遍历队列 if current == target { // 找到目标状态返回 return step } idx := 0 for current[idx] != '0' { // 找到0的索引 idx++ } for _, index := range neighbor[idx] { tmp := strings.Split(current, "") tmp[idx], tmp[index] = tmp[index], tmp[idx] // 交互数据索引 newStr := strings.Join(tmp, "") // 转换成新的字符 if _, ok := visited[newStr]; !ok { // 未访问过的放入到queue中 queue = append(queue, newStr) visited[newStr] = struct{}{} } } }
step++ // 增加步骤 }
return -1 }
t.Log(bfs())}
复制代码


用户头像

Dead or Alive. 生存战斗是知识的源泉! 2018.11.08 加入

我是一名SRE哨兵,目前是好大夫基础架构部高级工程师。专注于 SRE,微服务、中间件的稳定性和可用性建设,整体负责好大夫服务治理云平台的设计和搭建!

评论

发布
暂无评论
[Day45]-[BFS]-滑动谜题_LeetCode_方勇(gopher)_InfoQ写作社区