• LeetCode·每日一题·864.获取所有钥匙的最短路径·广度优先搜索

    作者：小迅
    链接：https://leetcode.cn/problems/shortest-path-to-get-all-keys/solutions/1960590/yan-du-you-xian-sou-suo-zhu-shi-chao-ji-75r4k/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

    题目

     

    示例

     

    思路

    正常的广度优先遍历只需要使用一个数组充当队列，并且用入参获取迭代结果就可以了，但是这个题需要记录的东西太多了。思路：

    • 想要走迷宫，最先想到的方法就是广度或者深度优先遍历，因为本题的目的是求最短路径，所以直观上广度更合适，满足条件后迭代的次数就是距离了；
    • 满足条件，是什么条件？不是走出迷宫，因为没有出口，也不是打开所有锁，而是收集齐所有的钥匙，所以我先遍历了一下数组，找到了钥匙的数量，接下来只要某次迭代获取的钥匙数量已经和这个值相同了，那就可以返回了，否则不能再迭代下去说明没有结果，返回-1。另外不知道有没有相关用例，但是因为没有说@的坐标就是（0，0），我在遍历过程中还获取了一下符号@的坐标作为起始点；
    • 那下面的难点就在怎么收集钥匙了，用广度优先遍历，每次遍历就相当于一种新的解法，为了防止无限循环，那就需要标记走过的路，可以在原来的数组上标记吗？不可以，因为多次选择路径必须分别记录，二维数组是满足不了这个需求的，至少要三维，其中两个维度依旧是坐标，剩下的维度实际上是钥匙的获取状态，一共6个钥匙，以一个整型变量的低6位记录状态，那不同的状态组合最多有2^6 - 1 = 63个，那么标记数组的最后一维大小就可以设置为63。
    • 那么接下来就是遍历的过程了：
      • 先将@符号入队，同时将什么符号都没有找到时的状态的@的坐标标记为1；
      • 开始将@上下左右的合法的节点入队，没有碰到钥匙的时候状态不变，无法倒退，但是一旦找到了一个钥匙，那对应的钥匙状态就改变了，可以倒退了；
      • 在面对不同的符号时操作有所不同，具体看注释吧；
      • 如果在某次迭代时发现已经找到了所有的钥匙，那就停止遍历，返回距离；但是如果发现没有新的节点入队，即队列为空了，就退出返回-1。 

    代码

    1.  
    2. // 位运算宏，包括获取某一位的值和设置某一位的值
    3. #define	GET_BIT(x, bit)	(((x) & (1 << (bit))) >> (bit))
    4. #define	SET_BIT(x, bit)	((x) |= (1 << (bit)))
    5. // 用于快速获取上下左右坐标
    6. int g_index[][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    7. // 用于统计钥匙数量，获取开始节点坐标，同时在队列节点里要记录当前找到的钥匙状态和路径长度
    8. int *getKeyNumAndStart(char ** grid, int gridSize, int colSize, int *keyNum)
    9. {
    10.     int *startIndex = (int *)malloc(sizeof(int) * 4);
    11.     for (int i = 0; i < gridSize; i++) {
    12.         for (int j = 0 ; j < colSize; j++) {
    13.             if (grid[i][j] >= 'a' && grid[i][j] <= 'f') {
    14.                 (*keyNum)++;
    15.             }
    16.             if (grid[i][j] == '@') {
    17.                 startIndex[0] = i;  // 开始节点坐标
    18.                 startIndex[1] = j;
    19.                 startIndex[2] = 0;  // 钥匙状态，都没找到就是0
    20.                 startIndex[3] = 0;  // 路径，一开始也是0
    21.             }
    22.         }
    23.     }
    24.     return startIndex;
    25. }
    26. // 获取当前已经找到的钥匙数量，需要统计低六位的1的数量
    27. int getCurKeyNum(int nodeKey)
    28. {
    29.     int keyNum = 0;
    30.     for (int i = 0; i < 6; i++) {
    31.         int num = GET_BIT(nodeKey, i);
    32.         keyNum += num;
    33.     }
    34.     return keyNum;
    35. }
    36. // 广度优先遍历
    37. void BFS(char ** grid, int **arrList, int start, int end, int keyNum, int *minPath, int ***visList,
    38.          int gridSize, int colSize)
    39. {
    40.     int startTemp = start;
    41.     int endTemp = end;
    42.     // 如果发现没有新的节点入队，即队列为空了，就退出返回-1
    43.     if (start >= end) {
    44.         return;
    45.     }
    46.     // 对该层节点进行遍历
    47.     for (int i = startTemp; i < endTemp; i++) {
    48.         // 获取一个节点
    49.         int *tempNode = arrList[i];
    50.         // 如果发现已经找到了所有钥匙，直接返回距离即可
    51.         int curKeyNum = getCurKeyNum(tempNode[2]);
    52.         if (curKeyNum == keyNum) {
    53.             *minPath = tempNode[3];
    54.             return;
    55.         }
    56.         // 否则继续
    57.         for (int j = 0; j < 4 ; j++) {
    58.             int x_temp = tempNode[0] + g_index[j][0];
    59.             int y_temp = tempNode[1] + g_index[j][1];
    60.             // 如果当前的节点坐标存在越界或者已经遍历过了，就跳过
    61.             if (x_temp < 0 || y_temp < 0 || x_temp >= gridSize || y_temp >= colSize ||
    62.                 visList[x_temp][y_temp][tempNode[2]] == 1) {
    63.                 continue;
    64.             }
    65.             // 遇到 ‘#’ 就标记遍历过就行了，实际不做操作就行，标记其实应该都没必要
    66.             if (grid[x_temp][y_temp] == '#') {
    67.                 visList[x_temp][y_temp][tempNode[2]] = 1;
    68.             }
    69.             // 遇到 “.” 或者“@”时（注意：有可能是反向跑回到起始点的，比如有的钥匙可能要绕一圈）
    70.             // 将节点入队，并标记标记数组中的对应位置
    71.             if (grid[x_temp][y_temp] == '.' || grid[x_temp][y_temp] == '@') {
    72.                 visList[x_temp][y_temp][tempNode[2]] = 1;
    73.                 arrList[end] = (int *)malloc(sizeof(int) * 4);
    74.                 arrList[end][0] = x_temp;
    75.                 arrList[end][1] = y_temp;
    76.                 arrList[end][2] = tempNode[2];
    77.                 arrList[end][3] = tempNode[3] + 1;
    78.                 end++;
    79.             }
    80.             // 遇到钥匙时，还是要标记一下当前状态的标记数组对应位置，但是状态马上就会改变；更新状态后将节点入队
    81.             if (grid[x_temp][y_temp] >= 'a' && grid[x_temp][y_temp] <= 'f') {
    82.                 visList[x_temp][y_temp][tempNode[2]] = 1;
    83.                 arrList[end] = (int *)malloc(sizeof(int) * 4);
    84.                 arrList[end][0] = x_temp;
    85.                 arrList[end][1] = y_temp;
    86.                 int temp = tempNode[2];
    87.                 SET_BIT(temp, grid[x_temp][y_temp] - 'a');
    88.                 arrList[end][2] = temp;
    89.                 arrList[end][3] = tempNode[3] + 1;
    90.                 end++;
    91.             }
    92.             // 遇到锁时，如果没钥匙，不做操作，如果有钥匙，就标记并入队
    93.             if (grid[x_temp][y_temp] >= 'A' && grid[x_temp][y_temp] <= 'F') {
    94.                 int temp = tempNode[2];
    95.                 if (GET_BIT(temp, grid[x_temp][y_temp] - 'A') == 1) {
    96.                     visList[x_temp][y_temp][tempNode[2]] = 1;
    97.                     arrList[end] = (int *)malloc(sizeof(int) * 4);
    98.                     arrList[end][0] = x_temp;
    99.                     arrList[end][1] = y_temp;
    100.                     arrList[end][2] = tempNode[2];
    101.                     arrList[end][3] = tempNode[3] + 1;
    102.                     end++;
    103.                 }
    104.             }
    105.         }
    106.         // 遍历过的节点出队
    107.         start++;
    108.     }
    109.     // 继续下一层的广度优先遍历
    110.     BFS(grid, arrList, start, end, keyNum, minPath, visList, gridSize, colSize);
    111.     return;
    112. }
    113. int shortestPathAllKeys(char ** grid, int gridSize){
    114.     int colSize = strlen(grid[0]);
    115.     int keyNum = 0;
    116.     // visList是标记数组，前两个维度是x，y轴坐标，后一个维度是钥匙状态，注意初始化
    117.     int ***visList = (int ***)malloc(sizeof(int **) * gridSize);
    118.     memset(visList, 0, sizeof(int **) * gridSize);
    119.     for (int i = 0; i < gridSize; i++) {
    120.         visList[i] = (int **)malloc(sizeof(int *) * colSize);
    121.         memset(visList[i], 0, sizeof(int *) * colSize);
    122.         for (int j = 0; j < colSize; j++) {
    123.             visList[i][j] = (int *)malloc(sizeof(int) * 63);
    124.             memset(visList[i][j], 0, sizeof(int) * 63);
    125.         }
    126.     }
    127.     // 充当队列的数组，数组元素包括坐标、当前找到的钥匙状态和走过的路径长度
    128.     int **arrList = (int **)malloc(sizeof(int *) * gridSize * colSize * 63);
    129.     memset(arrList, 0, sizeof(int *) * gridSize * colSize * 63);
    130.     // 获取开始节点的位置等信息
    131.     arrList[0] = getKeyNumAndStart(grid, gridSize, colSize, &keyNum);
    132.     // 初始化返回值
    133.     int minPath = -1;
    134.     // 标记数组中的首节点设为1
    135.     visList[arrList[0][0]][arrList[0][1]][arrList[0][2]] = 1;
    136.     // 开始广度优先遍历
    137.     BFS(grid, arrList, 0, 1, keyNum, &minPath, visList, gridSize, colSize);
    138.  
    139.     return minPath;
    140. }
    141.  
    142.  
    143.  
    144. 作者：小迅
    145. 链接：https://leetcode.cn/problems/shortest-path-to-get-all-keys/solutions/1960590/yan-du-you-xian-sou-suo-zhu-shi-chao-ji-75r4k/
    146. 来源：力扣（LeetCode）
    147. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

  • 相关阅读:
    java获取全国省市区信息
    LSTM Fully Convolutional Networks for Time Series Classification 学习记录
    WRF进阶：WRF中Noah-MP地面方案中雪反照率的计算
    AlexNet论文解读
    promise实现koa2洋葱中间件模型
    数学建模笔记-第九讲-分类模型-逻辑回归
    CMD命令终端快捷键学习
    haddop安装
    ADM 架构开发方法概述以及各个阶段的目的和交付物
    「React Native」为什么要选择 React Native 作为的跨端方案
  • 原文地址：https://blog.csdn.net/m0_64560763/article/details/127783202