#P2374. 推箱子

    ID: 1417 传统题 1000ms 128MiB 尝试: 24 已通过: 2 难度: 8 上传者: 标签>CF2400提高+/省选-A*可采纳估价函数广度优先搜索KM 算法状态编码状态去重可行性剪枝哈希表

推箱子

题目描述

推箱子是一个古老的游戏。在一个狭小的仓库中,要求控制小人的上下左右把木箱推到指定的位置。而且一次只能推动一个,胜利条件就是把所有的箱子都推到目的地。

小 Z 最近迷上了这个推箱子的游戏,可是玩了几关后发现,后边的相当地难通过,于是便需要你的帮助来通关。

输入格式

第 11 行,两个数 n,mn,m 分别表示地图有 nn 行 mm 列 (0≤n,m≤6)(0\le n,m\le 6)。

第 22 行到第 n+1n+1 行,每行 mm 个数,表示地图,其中 1 表示墙壁,2 表示箱子的位置,3 表示箱子的目的地,4 表示这个位置既是目的地,也有箱子,5 表示小人,0 则表示这里什么都没有,每个数都用空格空开。其中每个箱子可以推到任意一个目的地。

输出格式

一行,一个数,表示通关的最小步数,即小人移动的次数(由于方案不唯一,这里省去了输出方案)。

样例输入

6 6
1 5 0 1 1 1
1 0 2 0 0 1
1 1 0 1 0 1
3 1 0 1 0 0
3 2 0 0 1 0
3 0 0 0 2 0

样例输出

50

数据规模与约定

在所有数据中,0≤m,n≤60\le m,n\le 6。

数据保证人不会一开始站在目的地上,并保证都有解。