P13937 [蓝桥杯 2022 省 Java B] 拉箱子

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

第一行两个正整数 $N$ 和 $M$，表示网格的大小。 接下来 $N$ 行，每行 $M$ 个由空格隔开的整数 $0$ 或 $1$ 描述给定的地形。其中 $1$ 表示墙，$0$ 表示未知的元素，未知元素可能是小人或箱子或空地或终点，但不能是墙。

输出一个正整数，表示可解的初始局面数量。

**【样例说明】** 13 种可解的初始局面示意图如下： 人终箱空 墙墙墙空 --- 人终空箱 墙墙墙空 --- 人空终箱 墙墙墙空 --- 箱人终空 墙墙墙空 --- 空人终箱 墙墙墙空 --- 箱终人空 墙墙墙空 --- 空终人箱 墙墙墙空 --- 箱终空人 墙墙墙空 --- 箱空终人 墙墙墙空 --- 空箱终人 墙墙墙空 --- 箱终空空 墙墙墙人 --- 箱空终空 墙墙墙人 --- 空箱终空 墙墙墙人 --- **【评测用例规模与约定】** 对于 $30\%$ 的数据，$N, M \leq 3$. 对于 $100\%$ 的数据，$0 < N, M \leq 10$.