推箱子游戏——2002年第2期题解

问题描述见2002年第2期杂志。问题分析本题属于典型的状态空间搜索问题。 1.状态的表示通常可用精灵的坐标(rs,cs)和箱子的坐标(rb,cb)来表示状态。当精灵和箱子相邻时,状态可以用箱子的坐标(rb,cb)以及精灵和箱子的相对位置d表示为三元组(rb,cb,d),其中d=0、1、2、3分别表示东南西北四个方向,我们称这些状态为关键状态。例如图1中的两幅图分别表示为状态(2,1)、(2,3)和关键状态(2,3,2)。