1、题目描述

在这里插入图片描述

2、解题思路

本题是经典的BFS问题，对于任意一个状态 abcd，转动一次后的结果有 8 种，分别是：(a±1)bcd、a(b±1)cd、ab(c±1)d 和 abc(d±1)。

如果你只转一下锁，有几种可能？总共有 4 个位置，每个位置可以向上转，也可以向下转，也就是有 8 种可能对吧。

比如说从 “0000” 开始，转一次，可以穷举出 “1000”, “9000”, “0100”, “0900”… 共 8 种密码。然后，再以这 8 种密码作为基础，对每个密码再转一下，穷举出所有可能…

BFS 的核心思想应该不难理解的，就是把一些问题抽象成图，从一个点开始，向四周开始扩散。本题每一个状态的下一个状态有 8 种，也就是形成一个图，每个节点有 8 个相邻的节点。

直接采用 BFS 算法框架即可：

1、选择一个起点，本题是 0000；

2、定义一个队列用于存储待处理的节点；

3、定义一个 visited[] 数组存放已经处理过的节点；

4、while循环宽度遍历节点。

需要注意的地方是：0 往下转一次是 9，9 往上转一次是 0，即循环。同时，对于已经访问过的节点要进行判断，否则会死循环。

3、解题代码

// C 实现#include
   
    /* 从0000到9999最多10000个数字 */#define NUM_MAX 10000/* 向上拨，加 */int plusOne(int num, int place) {
       int ret = num;    if ((num / place) % 10 == 9) {
           ret -= place * 9;    } else {
           ret += place;    }    return ret;}/* 向下拨，减 */int minusOne(int num, int place) {
       int ret = num;    if ((num / place) % 10 == 0) {
           ret += place * 9;    } else {
           ret -= place;    }    return ret;}int strToInt(const char *str){
   	return (int)(str[0] - '0') * 1000 + 		(int)(str[1] - '0') * 100 +		(int)(str[2] - '0') * 10 +		(int)(str[3] - '0');}/* 开锁 */int openLock(char **deadends, int deadendsSize, char *target){
       /* 1、定义死亡数组deadendsList */    int deadendsList[NUM_MAX] = {
   0};    for (int i = 0; i < deadendsSize; i++) {
           deadendsList[strToInt(deadends[i])] = 1;    }    /* 若死亡数组包含初始值0000，则直接返回-1 */    if (deadendsList[0] == 1) {
           return -1;    }    /* 2、定义已遍历数组visited */    int visited[NUM_MAX] = {
   0};    /* 3、用数组来定义处理队列queue，头尾指针 */    int queue[NUM_MAX] = {
   0};    int head = 0, tail = 0;    /* 4、将target字符串转化为数字 */    int numtarget = strToInt(target);    /* 5、定义遍历步数step，将遍历初值0000填入队列、已遍历数组 */    int step = 0;    queue[tail++] = 0;    visited[0] = 1;    /* 6、从队头head遍历到队尾tail */    while (head < tail) {
           /* 6.1、计算当前队列长度 */        int size = tail - head;        /* 6.2、从队尾遍历到队头 */        for (int i = 0; i < size; i++) {
               /* 6.2.1、取出当前队头节点,并将队头移动一位 */              int cur = queue[head++];            /* 6.2.2、判断当前元素是否为target */            if (cur == numtarget) {
                   return step;            }            /* 6.2.3、进位数字numten */            int index = 1;            /* 6.2.4、遍历当前节点的8个相邻节点 */            for (int i = 1; i <= 4; i++) {
                   /* 向上拨，加 */                int up = plusOne(cur, index);                if (visited[up] != 1 && deadendsList[up] != 1) {
                       queue[tail++] = up;                    visited[up] = 1;                }                /* 向下拨，减 */                int down = minusOne(cur, index);                if (visited[down] != 1 && deadendsList[down] != 1) {
                       queue[tail++] = down;                    visited[down] = 1;                }                /* 进位数字乘10 */                index *= 10;            }        }        /* 6.3、遍历步数step++ */        step++;    }    /* 7、未发现target */    return -1;}

转载地址：http://ubtin.baihongyu.com/

你可能感兴趣的文章