拼多多校招算法迷宫路径

题目描述

一位探险家被困在地下的迷宫中，请从当前位置出发寻找通向迷宫出口的道路。该迷宫可用二维矩阵表示其内部结构，在其中一些路径上可能设置有门 lock 与其他字母 key 对应的钥匙 match 只有持有相应钥匙者方能开启这些门锁。
请设计一个算法来解决这一问题。

输入描述:

 迷宫的地图，用二维矩阵表示。第一行是表示矩阵的行数和列数M和N

    
 后面的M行是矩阵的数据，每一行对应与矩阵的一行（中间没有空格）。M和N都不超过100, 门不超过10扇。

输出描述:

    路径的长度，是一个整数

示例1

输入

复制

 5 5

    
 02111
    
 01a0A
    
 01003
    
 01001
    
 01111

输出

复制

    7

相较于普通问题而言，在本题中引入了钥匙这一状态维度。标识访问过的点及其对应的锁具状态的数组book[x][y][key]具有以下特点：其第一维x和第二维y分别代表横坐标与纵坐标的位置信息；第三维key则用于标识该位置处所拥有的锁具种类；锁具的状态采用二进制编码的方式进行表示；具体而言，在本问题中最多可拥有的不同锁具数量为10把（对应着2^10=1024种不同的锁具状态配置）