推箱子是一款经典电子游戏，爱丽丝很喜欢玩，但是她有点玩腻了，现在她想设计一款拉箱子游戏，拉箱子游戏需要玩家在一个 N × M 的网格地图中，控制小人上下左右移动，将箱子拉到终点以获得胜利，现在爱丽丝想知道，在给定地形的情况下，有多少种不同的可解的初始局面。
推箱子是一款经典电子游戏，爱丽丝很喜欢玩，但是她有点玩腻了，现在她想设计一款拉箱子游戏。 拉箱子游戏需要玩家在一个 N × M 的网格地图中，控制小人上下左右移动，将箱子拉到终点以获得胜利。 现在爱丽丝想知道，在给定地形（即所有墙的位置）的情况下，有多少种不同的可解的初始局面。 【初始局面】 的定义如下： 1、初始局面由排列成 N × M 矩形网格状的各种元素组成，每个网格中有且只有一种元素。可能的元素有：空地、墙、小人、箱子、终点。 2、初始局面中有且只有一个小人。 3、初始局面中有且只有一个箱子。 4、初始局面中有且只有一个终点。 【可解】 的定义如下： 通过有限次数的移动小人（可以在移动的同时拉箱子），箱子能够到达终点所在的网格。 【移动】 的定义如下： 在一次移动中，小人可以移动到相邻（上、下、左、右四种选项）的一个网格中，前提是满足以下条件： 1、小人永远不能移动到 N × M 的网格外部。 2、小人永远不能移动到墙上或是箱子上。 3、小人可以移动到空地或是终点上。 【拉箱子】 的定义如下： 在一次合法移动的同时，如果小人初始所在网格沿小人移动方向的反方向上的相邻网格上恰好是箱子，小人可以拉动箱子一起移动，让箱子移动到小人初始所在网格。 即使满足条件，小人也可以只移动而不拉箱子。
（图片来源网络，侵删）
