|
用STL实现DFS/BFS算法
——推箱子游戏(1)
推箱子的游戏想必很多朋友都有玩过，简单地说就是，在一个m*n的范围内有k个箱子和k个目的地，你只能使用推的方法来移动箱子，不能拖，也不能推动两个或以上的箱子，活动范围通常比较狭窄，还有一些不可移动的障碍物，所以有一定难度和可玩性。以下是一个中等难度的推箱子题目：
500)this.width=500'>
你可以看到，图的正中央是负责推箱子的“人” (Soko)；四周围住的是不可移动的障碍物(Wall)，中间也有一些；灰色的是空地(Space)；在Soko的右边是一个箱子(Box)，由于它不是在目的地上，所以用黄色来表示；它右下方的空地有一个紫红点，表示这是一个停放箱子的目的地(Dest)；在Soko的上方、左上方、右上方共有三个蓝色的箱子，表示这三个箱子已经放在目的地上了（不过为了把所有箱子都移动到目的地，这些已经放好的箱子也可以被移开）。所以，这道推箱子题目共有四个箱子和四个目的地。
首先，我们要决定如何在程序中表示推箱子问题的某个状态。我想到最简单的方法就是用一个m*n的二维char数组来表示，数组中的每一个char表示图中的一个格，格子可能是障碍物、人、箱子、目的地或空格，这几种状态也可能重叠，如人可以恰好站在一个目的地上，或者一个箱子恰好放在目的地上。我们用以下几个char来表示可能出现的格子状态：
CharWall = 'W', // Wall障碍物
CharBox = 'B', // Box箱子，不在目的地
CharSpace = 'S', // Space空地，没有任何东西
CharDest = 'D', // Dest目的地
CharInDest = 'I', // 已放在目的地上的箱子
CharSoko = 'K', // Soko推箱子的人，不在目的地
CharSokoInDest = 'O', // Soko推箱子的人，恰好在目的地
CharError = 'E' // 错误状态
用这种方法表示上面的题目，可以得到上图右侧的二维数组，行数和列数均为9。你可以看到左图并不是整整齐齐的二维图，它的最外围有一些缺口，我们在右图中全部用’W’来表示。这是显而易见的，它们没有什么作用，只是为了把图形填充为整齐的二维数组。如果你想用’S’来表示也无所谓，不会影响我们的程序执行，不过我想’W’更合适。
以上是一个推箱子问题状态的文本表示法，或者说是输入输出的方法，便于我们查看问题的状态。但是对于计算机程序处理来说，它并不是理想的表示方法，计算机更善于处理二进制的数字。所以我们还应该用二进制的方式来表示问题的状态，以便于程序的处理。同样的，我们还是使用二维数组来表示，不过这次数组的元素不是char字符，而是二进制的 unsigned char。经过简单的分析可以知道，一个格子可以用4个bit来表示所有状态：
FlagWall = 0x01, // 是否障碍物
FlagBox = 0x02, // 是否有箱子
FlagDest = 0x04, // 是否目的地
FlagSoko = 0x08 // 是否有人
在输入和输出问题状态时，需要进行这两种表示法之间的转换。即在输入时，把文本表示法转换为二进制表示法；在输出时，则把二进制表示法转换为文本表示法。这些都不难，后面会列出相关的代码。现在，我们先来给出问题状态类的定义。
和我们前面见到过的数独问题和N皇后问题一样，要使用DFS/BFS算法，我们需要设计问题状态类。对于推箱子问题，我们把问题状态类命名为SokoState，它的定义应该象下面这样：
class SokoState
{
public:
SokoState() : rows_(0), cols_(0) {}
void nextStep(vector<SokoState>&) const;
bool isTarget() const;
bool operator< (const SokoState& other) const;
friend ostream& operator<< (ostream& os, const SokoState& s);
friend istream& operator>> (istream& is, SokoState& s);
private:
struct SokoStep; //用于记录每一步箱子的移动
int rows_, cols_;
unsigned char map_[MAX_ROWS][MAX_COLS];
vector<SokoStep> steps_;
};
构造函数不必多说，在DFS/BFS算法中，问题状态类是要被放入STL容器中的，所以必须具备缺省构造函数。SokoState有四个成员变量：行数rows_、列数cols_、二维数组map_ 和一个vector容器变量steps_。前三个容易懂，正是我们前面说过的二进制表示法。最后一个steps_是什么呢？它正是推箱子问题与数独问题、 N皇后问题有明显区别的一点。
让我们回忆一下数独问题和N皇后问题，它们的问题状态类都仅记录了当前的状态数据，而且最终搜索到解答时，也只有最终的解答状态。至于如何从初始问题状态一步一步地变化到解答状态，这个过程并没有被记录下来。这是由于这两个问题都不关心状态的演变过程，它们只关心最终的解答状态。
但是对于推箱子问题则不能如此了，我们不仅要知道箱子最终能否被推到目的地，更重要的是，我们要知道箱子如何被一步一步地推到目的地。因此，我们需要在问题状态中记录从初始问题状态到解答状态所经过的每一步，这正是成员变量steps_的作用。我们用一个嵌套类SokoStep来表示一步移动，用vector<SokoStep>来表示所经过的N步移动。由于我们不知道从初始问题状态到解答状态需要经过多少步移动，这时vector容器就可以帮助我们很方便地保存每一步的数据。
由于我们所有四个成员变量都具有普通的值语义，所以编译器自动生成的拷贝构造函数、赋值操作符和析构函数都完全可用，我们可以省下不少功夫。不过后面还有很多事情要做，推箱子游戏可要比数独问题、N皇后问题难弄多了。
我们还是从容易的方面入手，先来搞定输入、输出操作符。正如前面所说的，输入输出的过程其实就是两种表示法的转换，先来看看输入操作符。由于二维数组的行数和列数也需要输入，所以我把它们放在最前面，接着是指定行数和列数的char阵列，阵列中的每个char必须是七个字符(“WBSDIKO”)中的一个，否则我们抛出一个异常来结束程序。每读入一个char，我们就根据该char（文本表示法）来设置map_数组的对应元素（二进制表示法）。以下是一个合法的输入文本（以前面的问题为例）：
9 9
WWWWWWWWW
WWWSSSWWW
WWSSSSSSW
WWIWIWISW
WWSWKBSWW
WWSWSWDWW
WSSSSSSWW
WSSSWSSWW
WWWWWWWWW
输入操作符的代码如下：
istream& operator>> (istream& is, SokoState& s)
{
is >> s.rows_;
if (s.rows_ < 4 || s.rows_ > MAX_ROWS)
{
throw invalid_argument("rows of soko game error.");
}
is >> s.cols_;
if (s.cols_ < 4 || s.cols_ > MAX_ROWS)
{
throw invalid_argument("cols of soko game error.");
}
string str;
getline(is, str); // 滤过第一行的换行
for (int i = 0; i < s.rows_; i++)
{
getline(is, str);
for (int j = 0; j < s.cols_; j++)
{
s.map_[i][j] = 0;
switch (str[j]) {
case SokoState::CharBox :
s.map_[i][j] |= SokoState::FlagBox;
break;
case SokoState::CharWall :
s.map_[i][j] |= SokoState::FlagWall;
break;
case SokoState::CharSpace :
break;
case SokoState::CharDest :
s.map_[i][j] |= SokoState::FlagDest;
break;
case SokoState::CharInDest :
s.map_[i][j] |= SokoState::FlagDest | SokoState::FlagBox;
break;
case SokoState::CharSoko :
s.map_[i][j] |= SokoState::FlagSoko;
break;
case SokoState::CharSokoInDest :
s.map_[i][j] |= SokoState::FlagSoko | SokoState::FlagDest;
break;
default :
throw invalid_argument(
string("char of soko game error: ") + str );
}
}
}
s.stateEq();
return is;
}
这里引入了一个新的成员函数stateEq()，它是干什么的呢？我们把它放一放，在输出操作符之后再作介绍。现在轮到输出操作符，即把二进制表示法转换为文本表示法。为了简化代码，我们先给出一些辅助成员函数：
class SokoState
{
public:
…
private:
struct Point
{
int x_, y_;
Point(int x, int y) : x_(x), y_(y) {}
Point up() { return Point(x_-1, y_); }
Point down() { return Point(x_+1, y_); }
Point left() { return Point(x_, y_-1); }
Point right() { return Point(x_, y_+1); }
};
enum MapChar {
CharWall = 'W', // Wall障碍物
CharBox = 'B', // Box箱子，不在目的地
CharSpace = 'S', // Space空地，没有任何东西
CharDest = 'D', // Dest目的地
CharInDest = 'I', // 已放在目的地上的箱子
CharSoko = 'K', // Soko推箱子的人，不在目的地
CharSokoInDest = 'O', // Soko推箱子的人，恰好在目的地
CharError = 'E' // 错误状态
};
enum MapFlag {
FlagWall = 0x01, // 是否障碍物
FlagBox = 0x02, // 是否有箱子
FlagDest = 0x04, // 是否目的地
FlagSoko = 0x08 // 是否有人
};
bool isWall(Point p) const
{ return (map_[p.x_][p.y_] & FlagWall) != 0; }
bool isBox(Point p) const
{ return (map_[p.x_][p.y_] & FlagBox) != 0; }
bool isDest(Point p) const
{ return (map_[p.x_][p.y_] & FlagDest) != 0; }
bool isSoko(Point p) const
{ return (map_[p.x_][p.y_] & FlagSoko) != 0; }
bool isSpace(Point p) const
{ return !isWall(p) && !isBox(p); }
bool isPureSpace(Point p) const
{ return isSpace(p) && !isSoko (p); }
unsigned char mapChar(Point p) const;
…
};
inline unsigned char SokoState::mapChar(Point p) const
{
if (isWall(p))
return CharWall;
else if (isBox(p))
return isDest(p) ? CharInDest : CharBox;
else if (isSoko(p))
return isDest(p) ? CharSokoInDest : CharSoko;
else if (isDest(p))
return CharDest;
else
return CharSpace;
}
这里我们引入了第二个嵌套类Point，用于表示二维图中的一个格，它有四个成员函数分别返回上下左右的格子。然后两个enum我们前面已经介绍过了，不再重复。接着是六个isXxxx函数，分别用于判断指定格子中是否有障碍物、箱子、人等。值得留意的是isSpace()和isPureSpace()的区别，前者可以表示格子中有人，而后者不行。最后，mapChar()成员函数用于返回指定格子的文本表示，即“WBSDIKO”之一。
有了这些辅助成员函数，我们的输出操作符就很简单了，如下：
ostream& operator<< (ostream& os, const SokoState& s)
{
char f, c;
for (int i = 0; i < s.rows_; i++)
{
for (int j = 0; j < s.cols_; j++)
{
os << s.mapChar(SokoState::Point(i, j));
}
os << "\n";
}
os << "------------------------" << endl;
return os;
}
现在我们回到stateEq()成员函数，它的作用是把SOKO（推箱子的人）在不推动箱子的前提下可以走到的位置（即他的自由活动范围）全部标记上FlagSoko。这样，我们在判断一个箱子能否移动时就可以简单一些了，只要这个箱子的某一侧为空格(Space)，而另一侧为FlagSoko，那么这个箱子就可以向空的一侧移动。还是以我们前面的问题为例子，经过stateEq()处理后的问题状态将变为：
500)this.width=500'>
stateEq()的实现原理是，从图中的SOKO位置开始对其上下左右的空格设置FlagSoko标志，然后对所有新的被设置FlagSoko标志的格子重复这一操作，直至没有新的格子被设置为止。处理中使用了STL的stack容器，代码如下：
void SokoState::stateEq()
{
int i, j;
for (i = 1; i < rows_-1; i++)
{
for (j = 1; j < cols_-1; j++)
{
if (isSoko(Point(i, j))) break;
}
if (j < cols_-1) break;
}
stack<Point> points;
Point p(i, j);
points.push(p);
while (!points.empty())
{
p = points.top();
points.pop();
checkSoko(points, p.up());
checkSoko(points, p.down());
checkSoko(points, p.left());
checkSoko(points, p.right());
}
}
void SokoState::checkSoko(stack<Point>& ps, Point p)
{
if (isPureSpace(p))
{
map_[p.x_][p.y_] |= FlagSoko;
ps.push(p);
}
} |
