算法题--⼴度优先算法（素数⾏李箱密码解法加步骤）
⽬录
⼴度优先算法思想
⼴度优先搜索使⽤队列（queue，先进先出）来实现，整个过程也可以看做⼀个倒⽴的树形：
1、把根节点放到队列的末尾。
2、每次从队列的头部取出⼀个元素，查看这个元素所有的下⼀级元素，把它们放到队列的末尾。
3、到所要的元素时结束程序。
4、如果遍历整个树还没有到，结束程序。
题⽬
素数⾏李箱密码
⼴度优先算法（BFS）、递归、哈希算法
题⽬描述
某⾏李箱⽀持4位数字密码，每位数字在0和9之间，开锁⽅式：
每次操作改变其中1位数字。（注意，是改变，⽐如0023改变第4位后，变成0029）每次操作后的数字必须始终是素数（如23和29是素数）。
现给定⾏李箱的初始密码与解锁密码（都是素数，包含前导0），请出最快的开锁⽅式（改变次数最少），输出改变次数，如果⽆法解锁，输出-1。
解答要求
时间限制：1000ms，内存限制：256MB
输⼊
两个4位数字字符，分别表⽰初始密码与解锁密码，以单个空格分隔。
输出
⼀个整数，表⽰开锁的最少改变次数；⽆法解锁则输出-1。
样例
输⼊样例1
0023 0059
输出样例1
2
提⽰样例1
0023->0059，存在两种开锁⽅式：0023->0029->0059，或0023->0053->0059，操作次数都是2
输⼊样例2
1373 8017，存在⼀种开锁⽅式：1373->0373->0313->0317->8317->8017，需要5次操作。
提⽰
素数，⼜称质数，指在⼤于1的⾃然数中，除了1和该数⾃⾝外，⽆法被其它⾃然数整除的数。答案
/
/定义队列，先进先出,⽤于⼴度优先算法
function Queue() {
this.q = new Array()
this.q.push(val)
}
this.deQueue = () => {
return this.q.shift()
}
this.isEmpty = () => {
return this.q.length === 0
}
this.size = () => {
return this.q.length
}
}
//判断是否为质数
const isPrime = (val) => {
var val = Number(val)
if (val === 0 || val === 1) {
return false
} else if (val === 2) {
return true
} else {
let t = Math.sqrt(val)
for (let i = 2; i <= t; i++) {
if (val % i === 0) {
return false
}
}
}
return true
}
/
/求只改变⼀位数字能产⽣多少个素数
const adjacent = (cur) => {
let nodes = []
let charators = cur.split('')
for (let i = 0; i < 4; i++) {
let iValue = Number(charators[i])
let copy = [...charators]
for (let j = 0; j <= 9; j++) {
copy[i] = j
if (j != iValue && isPrime(copy.join(''))) {
nodes.push(copy.join(''))
}
}
}
return nodes
}
const unlock = (initState, dstState) => {
let queue = new Queue()
//⽤于标记该密码是否已经使⽤过
let visited = {}
let sum = 0
visited[initState] = true
//队列不为空就继续循环
while (!queue.isEmpty()) {
let t = queue.size()
let xlNodes = []
//将现在队列中的每个数字拿出队列进⾏⼀次计算后再将符合条件的相邻素数放⼊队列
//将现在队列中的每个数字拿出队列进⾏⼀次计算后再将符合条件的相邻素数放⼊队列
for (let i = 0; i < t; i++) {
let cur = queue.deQueue()
//出⼝，到了密码
if (cur === dstState) {
return sum
}
//当前数字的相邻素数
xlNodes = adjacent(cur)
//将没有访问过的素数存⼊队列中，并标记为访问过
for (let j = 0; j < xlNodes.length; j++) {
if (!visited[xlNodes[j]]) {
visited[xlNodes[j]] = true
}
}
}
sum++
}
console.log(
unlock('1373', '8017')
)
解析
注意⽤到数组时，要使⽤浅拷贝。
核⼼思想
创建⼀个队列，每次从队列中拿出当前初始密码，计算相邻的素数密码后全部放⼊队列，并将放⼊过队列的密码标记。每次放⼊队列前要进⾏判断，未做标记的才能放⼊。循环直到队列为空（不到密码）或到密码。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论