8.6 Implement a jigsaw puzzle. Design the data structures and explain an algorithm to solve the puzzle. You can assume that you have a f itsWith method which, when passed two puzzle pieces, returns true if the two pieces belong together.
这道题让我们设计一个拼图游戏，根据书上的解释，如上图所示是一种最基本的拼图游戏，每一片有四条边，总共有三种边，inner, outer, 和 flat的，角落的一片有两个flat的边，中间的片没有flat的边。那么我们需要一个边类Edge，还需要一个片类Piece，和一个拼图类Puzzle，在拼图类里用sort来初始化参数，再用solve来完成拼图。这里不得不吐槽一下，这道题在网上下载的代码里面都木有，而且书上的代码有很多小错误，改正后参见代码如下：
class Edge;
class Piece {
public:
vector
bool isCorner() {} // ...
};
enum Type { inner, outer, flat };
class Edge {
public:
Piece *_parent;
Type _type;
int _index;
Edge *_attachedTo;
bool fitsWith(Edge *edge) {} // ...
};
class Puzzle {
public:
vector
vector
vector
vector
void sort() {
for (Piece *p : _pieces ) {
if (p->isCorner()) _corners.push_back(p);
for (Edge *e : p->_edges) {
if (e->_type == Type::inner) _inners.push_back(e);
if (e->_type == Type::outer) _outers.push_back(e);
}
}
}
void solve() {
Edge *currentEdge = getExposedEdge(_corners[0]);
while (currentEdge != nullptr) {
vector
for (Edge *e : opposites) {
if (currentEdge->fitsWith(e)) {
attachEdges(currentEdge, e);
removeFromList(currentEdge);
removeFromList(e);
currentEdge = nextExposedEdge(e);
break;
}
}
}
}
void removeFromList(Edge *edge) {
if (edge->_type == Type::flat) return;
vector
for (vector
if (*it == edge) {
array.erase(it);
break;
}
}
}
Edge* nextExposedEdge(Edge *edge) {
int next_idx = (edge->_index + 2) % 4; // Opposite edge
Edge *next_edge = edge->_parent->_edges[next_idx];
if (isExposed(next_edge)) {
return next_edge;
}
return getExposedEdge(edge->_parent);
}
void attachEdges(Edge *e1, Edge *e2) {
e1->_attachedTo = e2;
e2->_attachedTo = e1;
}
bool isExposed(Edge *edge) {
return edge->_type != Type::flat && edge->_attachedTo == nullptr;
}
Edge* getExposedEdge(Piece *p) {
for (Edge *e : p->_edges) {
if (isExposed(e)) return e;
}
return nullptr;
}
};
发表评论