推箱子是一个古老的游戏。在一个狭小的仓库中,要求控制小人的上下左右把木箱推到指定的位置。而且一次只能推动一个,胜利条件就是把所有的箱子都推到目的地。
小Z最近迷上了这个推箱子的游戏,可是玩了几关后发现,后边的相当地难通过,于是便需要你的帮助来通关。
第1行,两个数n,m分别表示地图有n行m列。(0<=n,m<=6) 第2行到第n+1行,每行m个数,表示地图,其中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<=6
数据保证人不会一开始站在目的地上,并保证都有解。