第一步,抽离有用状态
第二步,有用状态与有用的后继状态 连边构图,
边权为:由有用状态 到 后继状态 所需的最小步数
第三步,初始状态 到 目标状态 ,跑最短路(最好是跑 spfaspfaspfa )
我们可以用 000 , 111 , 222 , 333 分别表示空白格在指定格的上右下左
状态 === ((行号 −1-1−1 )列数 +++ (列号 −1-1−1 )) 4+4+4+ 000 / 111 / 222 / 333
intintint numbersnumbersnumbers ( intintint iii , intintint jjj ) { returnreturnreturn ( i−1i-1i−1 )* m+j−1<<2m+j-1<<2m+j−1<<2 ; } 状态 =number=number=number ( xxx , yyy ) +0+0+0 / 111 / 222 / 333
其实所有网格图中的状态都可以采取类似的方法
状态编号 === 图中编号* S+S+S+ xxx , xxx ∈[ 000 , SSS ) S=S=S= 每种编号状态数
所以在定义 dxdxdx 数组跟 dydydy 数组的时候一定要一一对应