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<Edge*> _edges; 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<Piece*> _pieces; vector<vector<Piece*> > _solution; vector<Edge*> _inners, _outers, _flats; vector<Piece*> _corners; 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<Edge*> opposites = currentEdge->_type == Type::inner ? _outers : _inners; 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<Edge*> array = edge->_type == Type::inner ? _inners : _outers; for (vector<Edge*>::iterator it = array.begin(); it != array.end(); ++it) { 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; } };
本文转自博客园Grandyang的博客，原文链接：拼图游戏[CareerCup] 8.6 Jigsaw Puzzle ，如需转载请自行联系原博主。
