上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution {
public:
int slidingPuzzle(vector<vector<int>>& board) {
}
};
golang 解法, 执行用时: 4 ms, 内存消耗: 3.3 MB, 提交时间: 2023-01-09 15:37:19
type astar struct {
g, h int
status string
}
type hp []astar
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].g+h[i].h < h[j].g+h[j].h }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{}) { *h = append(*h, v.(astar)) }
func (h *hp) Pop() interface{} { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
// 曼哈顿距离
var dist = [6][6]int{
{0, 1, 2, 1, 2, 3},
{1, 0, 1, 2, 1, 2},
{2, 1, 0, 3, 2, 1},
{1, 2, 3, 0, 1, 2},
{2, 1, 2, 1, 0, 1},
{3, 2, 1, 2, 1, 0},
}
// 计算启发函数
func getH(status string) (ret int) {
for i, ch := range status {
if ch != '0' {
ret += dist[i][ch-'1']
}
}
return
}
var neighbors = [6][]int{{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}}
func slidingPuzzle(board [][]int) int {
const target = "123450"
s := make([]byte, 0, 6)
for _, r := range board {
for _, v := range r {
s = append(s, '0'+byte(v))
}
}
start := string(s)
if start == target {
return 0
}
// 枚举 status 通过一次交换操作得到的状态
get := func(status string) (ret []string) {
s := []byte(status)
x := strings.Index(status, "0")
for _, y := range neighbors[x] {
s[x], s[y] = s[y], s[x]
ret = append(ret, string(s))
s[x], s[y] = s[y], s[x]
}
return
}
type pair struct {
status string
step int
}
h := hp{{0, getH(start), start}}
seen := map[string]bool{start: true}
for len(h) > 0 {
node := heap.Pop(&h).(astar)
for _, nxt := range get(node.status) {
if !seen[nxt] {
if nxt == target {
return node.g + 1
}
seen[nxt] = true
heap.Push(&h, astar{node.g + 1, getH(nxt), nxt})
}
}
}
return -1
}
python3 解法, 执行用时: 52 ms, 内存消耗: 15.1 MB, 提交时间: 2023-01-09 15:36:55
# 启发式搜索
class AStar:
DIST = [
[0, 1, 2, 1, 2, 3],
[1, 0, 1, 2, 1, 2],
[2, 1, 0, 3, 2, 1],
[1, 2, 3, 0, 1, 2],
[2, 1, 2, 1, 0, 1],
[3, 2, 1, 2, 1, 0],
]
# 计算启发函数
@staticmethod
def getH(status: str) -> int:
ret = 0
for i in range(6):
if status[i] != "0":
ret += AStar.DIST[i][int(status[i]) - 1]
return ret
def __init__(self, status: str, g: str) -> None:
self.status = status
self.g = g
self.h = AStar.getH(status)
self.f = self.g + self.h
def __lt__(self, other: "AStar") -> bool:
return self.f < other.f
class Solution:
NEIGHBORS = [[1, 3], [0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4]]
def slidingPuzzle(self, board: List[List[int]]) -> int:
# 枚举 status 通过一次交换操作得到的状态
def get(status: str) -> Generator[str, None, None]:
s = list(status)
x = s.index("0")
for y in Solution.NEIGHBORS[x]:
s[x], s[y] = s[y], s[x]
yield "".join(s)
s[x], s[y] = s[y], s[x]
initial = "".join(str(num) for num in sum(board, []))
if initial == "123450":
return 0
q = [AStar(initial, 0)]
seen = {initial}
while q:
node = heapq.heappop(q)
for next_status in get(node.status):
if next_status not in seen:
if next_status == "123450":
return node.g + 1
heapq.heappush(q, AStar(next_status, node.g + 1))
seen.add(next_status)
return -1
javascript 解法, 执行用时: 68 ms, 内存消耗: 44.1 MB, 提交时间: 2023-01-09 15:36:21
/**
* @param {number[][]} board
* @return {number}
*/
var slidingPuzzle = function(board) {
const neighbors = [[1, 3], [0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4]];
const sb = [];
for (let i = 0; i < 2; ++i) {
for (let j = 0; j < 3; ++j) {
sb.push(board[i][j]);
}
}
const initial = sb.join('');
if ("123450" === initial) {
return 0;
}
let step = 0;
const queue = [];
queue.push(initial);
const seen = new Set();
seen.add(initial);
// 枚举 status 通过一次交换操作得到的状态
const get = (status) => {
const ret = [];
const array = Array.from(status);
const x = status.indexOf('0');
for (const y of neighbors[x]) {
[array[x], array[y]] = [array[y], array[x]];
ret.push(array.join(''));
[array[x], array[y]] = [array[y], array[x]];
}
return ret;
}
while (queue.length) {
++step;
const size = queue.length;
for (let i = 0; i < size; ++i) {
const status = queue.shift();
for (const nextStatus of get(status)) {
if (!seen.has(nextStatus)) {
if ("123450" === nextStatus) {
return step;
}
queue.push(nextStatus);
seen.add(nextStatus);
}
}
}
}
return -1;
};
golang 解法, 执行用时: 4 ms, 内存消耗: 3.5 MB, 提交时间: 2023-01-09 15:35:52
// 广度优先搜索
var neighbors = [6][]int{{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}}
func slidingPuzzle(board [][]int) int {
const target = "123450"
s := make([]byte, 0, 6)
for _, r := range board {
for _, v := range r {
s = append(s, '0'+byte(v))
}
}
start := string(s)
if start == target {
return 0
}
// 枚举 status 通过一次交换操作得到的状态
get := func(status string) (ret []string) {
s := []byte(status)
x := strings.Index(status, "0")
for _, y := range neighbors[x] {
s[x], s[y] = s[y], s[x]
ret = append(ret, string(s))
s[x], s[y] = s[y], s[x]
}
return
}
type pair struct {
status string
step int
}
q := []pair{{start, 0}}
seen := map[string]bool{start: true}
for len(q) > 0 {
p := q[0]
q = q[1:]
for _, nxt := range get(p.status) {
if !seen[nxt] {
if nxt == target {
return p.step + 1
}
seen[nxt] = true
q = append(q, pair{nxt, p.step + 1})
}
}
}
return -1
}
python3 解法, 执行用时: 44 ms, 内存消耗: 14.9 MB, 提交时间: 2023-01-09 15:35:20
# 深度优先搜索
class Solution:
NEIGHBORS = [[1, 3], [0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4]]
def slidingPuzzle(self, board: List[List[int]]) -> int:
# 枚举 status 通过一次交换操作得到的状态
def get(status: str) -> Generator[str, None, None]:
s = list(status)
x = s.index("0")
for y in Solution.NEIGHBORS[x]:
s[x], s[y] = s[y], s[x]
yield "".join(s)
s[x], s[y] = s[y], s[x]
initial = "".join(str(num) for num in sum(board, []))
if initial == "123450":
return 0
q = deque([(initial, 0)])
seen = {initial}
while q:
status, step = q.popleft()
for next_status in get(status):
if next_status not in seen:
if next_status == "123450":
return step + 1
q.append((next_status, step + 1))
seen.add(next_status)
return -1
