LeetCode 773. 滑动谜题

Categories:

题目描述
思路分析
1. 解法一：BFS（推荐）
相似题目

题目描述

✅ 773. 滑动谜题

思路分析

解法一：BFS（推荐）

核心思路：

将 2x3 棋盘编码为字符串状态。

BFS 扩展所有可交换位置，找到目标状态。

使用集合去重避免重复访问。

复杂度分析：

时间复杂度：O(6!)，状态空间固定。

空间复杂度：O(6!)，用于队列与访问集合。

import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.Queue;
import java.util.Set;

class Solution {
    public int slidingPuzzle(int[][] board) {
        StringBuilder start = new StringBuilder();
        for (int[] row : board) {
            for (int v : row) {
                start.append(v);
            }
        }

        String target = "123450";
        int[][] neighbors = {
                {1, 3},
                {0, 2, 4},
                {1, 5},
                {0, 4},
                {1, 3, 5},
                {2, 4}
        };

        Queue<String> queue = new ArrayDeque<>();
        Set<String> visited = new HashSet<>();
        queue.offer(start.toString());
        visited.add(start.toString());

        int steps = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String cur = queue.poll();
                if (cur.equals(target)) {
                    return steps;
                }

                int zero = cur.indexOf('0');
                for (int next : neighbors[zero]) {
                    String nextState = swap(cur, zero, next);
                    if (visited.add(nextState)) {
                        queue.offer(nextState);
                    }
                }
            }
            steps++;
        }

        return -1;
    }

    private String swap(String s, int i, int j) {
        char[] chars = s.toCharArray();
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;
        return new String(chars);
    }
}

import "strings"

func slidingPuzzle(board [][]int) int {
	start := make([]byte, 0, 6)
	for _, row := range board {
		for _, v := range row {
			start = append(start, byte('0'+v))
		}
	}

	target := "123450"
	neighbors := [][]int{
		{1, 3},
		{0, 2, 4},
		{1, 5},
		{0, 4},
		{1, 3, 5},
		{2, 4},
	}

	queue := make([]string, 0)
	visited := make(map[string]struct{})
	queue = append(queue, string(start))
	visited[string(start)] = struct{}{}

	steps := 0
	for len(queue) > 0 {
		size := len(queue)
		for i := 0; i < size; i++ {
			cur := queue[0]
			queue = queue[1:]
			if cur == target {
				return steps
			}

			zero := strings.IndexByte(cur, '0')
			for _, next := range neighbors[zero] {
				nextState := swapStr(cur, zero, next)
				if _, ok := visited[nextState]; !ok {
					visited[nextState] = struct{}{}
					queue = append(queue, nextState)
				}
			}
		}
		steps++
	}

	return -1
}

func swapStr(s string, i int, j int) string {
	chars := []byte(s)
	chars[i], chars[j] = chars[j], chars[i]
	return string(chars)
}

相似题目

题目	难度	考察点
752. 打开转盘锁	中等	BFS
1091. 二进制矩阵中的最短路径	中等	BFS
200. 岛屿数量	中等	BFS/DFS
127. 单词接龙	困难	BFS
490. 迷宫	中等	BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/43212310