题目和原解法
原文用py和循环15步完成, 其实这个比较简单, 没啥可玩的, 重点在于思路
状态由三个, 不能使用位运算, 但是可以使用十进制的每个位
首先用数组表示实属有点浪费, 哪怕是字符串呢, 不过数组确实操作方便, 这个题目的搜索难度也不大所以用啥都行, 最好是封装位运算或者字符串, 这样判断是否阻塞也方便
对于每一次搜索, 所有可以进行的操作就是一步, 然后深搜即可, 每进一步执行操作更新状态, 每撤销一步恢复状态, 由于状态就是数字, 不会有引用问题
由于每次操作数目有限, 目测应该是指数级
本来不想写的... 不过实在没啥事干就用js实现下吧...
深搜简单实现下, 每加阻塞判断和优化, 跑出来的结果也是15, 一共只有两个解... 原文中给的是第二个解
[
[
2223133, 2213233, 2123233,
2321233, 2323213, 2323231,
2323132, 2313232, 1323232,
3123232, 3321232, 3323212,
3323122, 3313222, 3331222
],
[
2212333, 2232133, 2232313,
2231323, 2132323, 1232323,
3212323, 3232123, 3232321,
3232312, 3231322, 3132322,
3312322, 3332122, 3331222
]
]
const white = 2
const blank = 1
const black = 3
const moveType = {
left: 0, // 左移
leftJump: 1, // 左跳
right: 2, // 右移
rightJump: 3, // 右跳
}
// 由低位到高位 1:空格,2:白,3:黑
const show = n => {
console.log(
toList(n)
.reverse()
.join("-"),
)
}
const toList = n =>
Array(7)
.fill(0)
.map((_, i) => ((n / 10 ** i) | 0) % 10)
/*
2 2 2 1 3 3 3
index 0 1 2 3 4 5 6
value 3 3 3 1 2 2 2
*/
initState = 2221333
show(initState) // 2-2-2-1-3-3-3
// 是否满足终止条件
const check = n => {
return n === 3331222
}
const showStop = n => {
return false
}
const get = (n, index) => ((n / 10 ** index) | 0) % 10
const set = (n, index, value) =>
n - get(n, index) * 10 ** index + value * 10 ** index
const exchange = (n, from, to) => {
const fv = get(n, from)
const tv = get(n, to)
return set(set(n, from, tv), to, fv)
}
const doMove = (n, { type, index }) => {
if (type === moveType.left) {
return exchange(n, index, index + 1)
} else if (type === moveType.leftJump) {
return exchange(n, index, index + 2)
} else if (type === moveType.right) {
return exchange(n, index, index - 1)
} else if (type === moveType.rightJump) {
return exchange(n, index, index - 2)
}
}
const indexArray = Array(7)
.fill(0)
.map((_, k) => k)
// 获取可操作的集合
const getOpList = n => {
// 空格所在位置
const blankIndex = indexArray.find(i => get(n, i) === blank)
console.log("blankIndex", blankIndex)
const list = []
for (let i = 0; i < 7; i++) {
if (i === blankIndex) continue
if (get(n, i) === black) {
if (i + 1 < 7 && i + 1 === blankIndex) {
// 黑左移
list.push({
type: moveType.left,
index: i,
})
} else if (i + 2 < 7 && get(n, i + 1) === white && i + 2 === blankIndex) {
// 黑左跳
list.push({
type: moveType.leftJump,
index: i,
})
}
} else {
if (i >= 1 && i - 1 === blankIndex) {
// 白右移
list.push({
type: moveType.right,
index: i,
})
} else if (i >= 2 && get(n, i - 1) === black && i - 2 === blankIndex) {
// 白右跳
list.push({
type: moveType.rightJump,
index: i,
})
}
}
}
return list
}
// 是否存在阻塞
const shouldStop = () => {}
const answer = []
const dfs = (n, path = []) => {
console.log("dfs", n, path.length)
if (check(n)) {
console.log(path.length, path)
answer.push([...path])
return true
}
if (shouldStop(n)) {
// 存在阻塞
return false
}
const list = getOpList(n)
// 获取所有可以执行的操作
for (const op of list) {
// 进行操作
console.log(op)
path.push(doMove(n, op))
const res = dfs(doMove(n, op), path)
path.pop()
if (res) {
// return true
}
}
return false
}
dfs(initState)
console.log(answer)
