Единственно подходящим завершением главы о поиске решений представляется создание программы поиска ключей от машины из первого примера. В приведенном в листинге 7.8 коде использованы те же технические приемы, что и программах поиска маршрута между городами, поэтому он дан без последующих пояснений.
{ Листинг 7.8. Поиск потерянных ключей
#include <ioscream> #include <stack> #include <string> #include <vector>
using namespace std;
// Информация о комнате, struct Roomlnfo {
string from,-
string to;
bool skip;
RoomlnfoO { from - "";
to = "";
skip = false;
}
. Roamlnfо(string f. string t) { from = f; to = t; skip = false;
}
};
// Ищет ключи, используя поиск в глубину, class Search {
// Этот вектор содержит информацию о комнатах.
vector<RoomInfo> rooms;
// Этот стек применяется для возврата. stack<RoamInfo> btStack;
// Возвращает true, если существует путь между
// from и to. Возвращает false в противном случае.
bool match(string from, string to);
// При заданном from находит любой путь. // Возвращает true, если путь найден, // и false — в противном случае, bool find(string from, Roomlnfo &f);
public:
// Помещает сведения о комнатах в базу данных.
void addroom(string from, string to)
{
rooms.push_back(Roomlnfo(from, to));
}
// Показывает пройденный маршрут. void route();
// Определяет, есть ли путь между from и to. void findkeys(string from, string to);
// Возвращает true, если ключи были найдены, bool keysfound() {
return !btStack.empty();
}
};
// Показывает маршрут, void Search::route() {
stack<RoomInfo> rev; Roomlnfo f;
// Меняет порядок стека на обратный для отображения маршрута, while(!btStack.empty()) (
f = btStack.topO ;
rev.push(f);
btStack.pop4);
}
// Отображает маршрут, while(!rev.empty()) {
f = rev.top();
rev.pop() ;
cout « f.from « " to ";
}
cout « f.to « endl;
}
// Возвращает true, если существует путь между
// from и to. Возврашает false в противном случае.
bool Search::match(string from, string to)
{
for(unsigned i=0; i < rooms.size(); i++) { if(rooms[i].from == from &&
rooms[i].to == to && !rooms[i].skip)
{
rooms[i].skip = true; // предотвращает повторное использование return true;
}
}
return false; //не найлен
}
// При заданном from находит какой-нибудь путь.
// Возвращает true, если путь найден,
//и false — в противном случае.
bool Search::find(string from, Roomlnfo &f)
{
for(unsigned i=0; i < rooms.size(); i++) {
if (rooms [i]. from == from && !rooms [i] .skip) { f = rooms [i];
rooms[i].skip = true; // предотвращает повторное использование return true;
}
}
return false;
}
// Ищет ключи.
void Search::findkeys(string from, string to) {
Roomlnfo f;
// Проверяет, найдены ли ключи, if (match (from, to)) {
btStack.push(Roomlnfo(from, to)); • return; }
// Проверяет другую комнату, if(find(from, f)) {
btstack.push(Roomlnfo(from, to));
findkeys(f.to, to);
}
else i f(!btStack.empcy()) {
// Возвращается и пробует другой путь.
f = btStack.top() ; btStack.popO ; findkeys(f.from, f.to);
}
}
int main() Search ob;
// Добавляет комнаты в базу данных, ob.addroom ("front_door", "lrn); ob.addroom ("lrn, "bath"); ob.addroom ("lrn, "hall"); ob.addroom("hall", "bdl"); ob.addroom("hall", "bd2"); ob.addroom ("hall", "mb"); ob.addroom("lr", "ki tcheh"); ob.addroom ("ki tchen", "keys");
// Ищет ключи.
ob. f indkeys (" f ront_door", " keys ") ; // Если ключи найдены, показывает путь, if(ob.keysfound()) ob.route();
return 0;
}
|
