目录

广度优先算法思想

题目

素数行李箱密码

题目描述

解答要求

答案

解析

核心思想

广度优先算法思想

广度优先搜索使用队列（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.enQueue = (val) => {
        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
    queue.enQueue(initState)
    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]]) {
                    queue.enQueue(xlNodes[j])
                    visited[xlNodes[j]] = true
                }
            }
        }
        sum++
    }
console.log(
    unlock('1373', '8017')
)

解析

注意用到数组时，要使用浅拷贝。

核心思想

创建一个队列，每次从队列中拿出当前初始密码，计算相邻的素数密码后全部放入队列，并将放入过队列的密码标记。每次放入队列前要进行判断，未做标记的才能放入。循环直到队列为空（找不到密码）或找到密码。