2018百度之星复赛E题　棋盘上的旅行

未分类

概率算法

题意:
在一个$n*m$的棋盘上,每个格子有一个值$a_{ij}$,$a_{ij}>0$表示该点的颜色是$a_{ij}$,$a_{ij}=0$表示该点没有颜色,$a_{ij}=-1$表示该点是障碍物不能经过.
求解从任意一点出发,经过$k$种不同颜色的格子最少需要走多少步,每步只能走到相邻的格子.
数据范围$(1\leq n,m \leq 20, -1 \leq a_{i,j} \leq n*m, 1\leq k \leq 7)$.

解析:

总共最多有$n*m$种颜色,但是对求解题目来说只有其中$k$种颜色是有影响的,所以可以把这$n*m$映射成$k$种颜色,然后对映射后的格子求解.假设最优答案存在,那么单次映射成最优答案的概率最低是$\frac{k!}{k^k}$,当$k=7$的时候这个值最小,约为$0.006$,那么进行$1000$次这个过程,没有一个映射到正确答案的概率是$0.002$,也就是映射到最优答案的概率是$99.8\%$.
现在只需要考虑有$k$种颜色的情况.
对棋盘中每个点记录一个状态$S$,$S$是一个二进制码.
记录$dis(i,j,S)$,表示经过集合$S$的颜色后到达$(i,j)$点最少需要的步数,那么在棋盘上面跑最短路即可,最多$n*m*2^k$个点.