Breadth First Search решит эту проблему.
Запишите статус (room, credit), когда Карли прибыла в комнату с номером room со значением кредита, записанным в credit.
Использование queue для хранения данных. Вначале в очереди находится только (снаружи, 0). Каждый раз выталкивайте голову и переходите из состояния, описанного head, в каждую соседнюю комнату head, затем вычисляйте новый статус и вставляйте их в конец queue (не забудьте использовать хэш, чтобы избежать добавления одного и того же статуса). чем один раз).
Когда вы достигнете статуса (exam, 214), процесс развертывания завершится. Остается вернуться назад из состояния (exam, 214). При получении нового статуса в BFS вы также можете записать указатель на статус-предшественник.
Вот мой код.
char name[][15] = {
"exam",
"stochastic",
"modeling",
"calculus",
"math",
"modern arts",
"algebra",
"philosophy",
"outside"
};
int credits[]={0, 23, 29, 20, 17, 17, 35, 32, 0};
int neighbour[][7]={
{ 1, 2, -1},
{ 2, 3, -1},
{ 0, 1, 3, 4, 5, -1},
{ 1, 2, 4,-1},
{ 2, 3, 6, -1},
{ 2, 6, 7, -1},
{ 4, 5, 7, -1},
{ 5, 6, -1},
{ 4, -1}
};
class Node{
public:
int pos;
int credit;
bool operator <( const Node a) const{
return pos < a.pos || pos == a.pos && credit < a.credit;
}
};
vector<Node> Q;
vector<int> pred;
set<Node> hash;
void bfs(){
int n = 9;
bool found = false;
hash.clear();
Node start;
start.pos = 8, start.credit = 0;
Q.push_back(start);
pred.push_back(-1);
hash.insert(start);
for(int f=0; f<Q.size(); ++f){
Node head = Q[f];
int pos = head.pos;
//printf("%d %d -> \n", head.pos, head.credit);
for(int i=0; neighbour[pos][i]!=-1; ++i){
Node tmp;
tmp.pos = neighbour[pos][i];
tmp.credit = head.credit + credits[tmp.pos];
if(tmp.credit > 214) continue;
if(hash.count(tmp)) continue;
if(tmp.credit !=214 && tmp.pos==0)continue; // if the credit is not 214, then it is not allowed to enter exame room(numbered as 0)
Q.push_back(tmp);
pred.push_back(f);
//printf(" -> %d, %d\n", tmp.pos, tmp.credit);
if(tmp.credit==214 && tmp.pos==0){
found = true;
break;
}
}
if(found)break;
}
stack<int> ss;
int idx = Q.size()-1;
while(true){
ss.push(Q[idx].pos);
if(pred[idx]!=-1) idx=pred[idx];
else break;
}
for(int credit=0; ss.size() > 0; ){
int pos = ss.top();
credit += credits[pos];
printf("%s(%d) ", name[pos], credit);
ss.pop();
}
printf("\n");
}
UPD1: Извините, я допускаю ошибки при присвоении значений neighbour[]. Я исправил это.
UPD1: Извините, я забыл проверить, равен ли балл 214 при входе в экзаменационную комнату. Я исправил это.
UPD3: @Nuclearman говорит, что не дает всех решений. Нам нужно только удалить hash из кода и вычислить путь при создании нового статуса с кредитом 214. Здесь я привожу новый код.
char name[][15] = {
"exam",
"stochastic",
"modeling",
"calculus",
"math",
"modern arts",
"algebra",
"philosophy",
"outside"
};
int credits[]={0, 23, 29, 20, 17, 17, 35, 32, 0};
int neighbour[][7]={
{ 1, 2, -1},
{ 2, 3, -1},
{ 0, 1, 3, 4, 5, -1},
{ 1, 2, 4,-1},
{ 2, 3, 6, -1},
{ 2, 6, 7, -1},
{ 4, 5, 7, -1},
{ 5, 6, -1},
{ 4, -1}
};
class Node{
public:
int pos;
int credit;
bool operator <( const Node a) const{
return pos < a.pos || pos == a.pos && credit < a.credit;
}
};
vector<Node> Q;
vector<int> pred;
set<Node> hash;
void outputpath(){
stack<int> ss;
int idx = Q.size()-1;
while(true){
ss.push(Q[idx].pos);
if(pred[idx]!=-1) idx=pred[idx];
else break;
}
for(int credit=0; ss.size() > 0; ){
int pos = ss.top();
credit += credits[pos];
printf("%s(%d) ", name[pos], credit);
ss.pop();
}
printf("\n");
}
void bfs(){
int n = 9;
bool found = false;
hash.clear();
Node start;
start.pos = 8, start.credit = 0;
Q.push_back(start);
pred.push_back(-1);
hash.insert(start);
for(int f=0; f<Q.size(); ++f){
Node head = Q[f];
int pos = head.pos;
for(int i=0; neighbour[pos][i]!=-1; ++i){
Node tmp;
tmp.pos = neighbour[pos][i];
tmp.credit = head.credit + credits[tmp.pos];
if(tmp.credit > 214) continue;
if(hash.count(tmp)) continue;
if(tmp.credit !=214 && tmp.pos==0)continue;
Q.push_back(tmp);
pred.push_back(f);
if(tmp.credit==214 && tmp.pos==0){
outputpath();
/* uncomment the next line to get only one solution*/
//found = true;
break;
}
}
if(found)break;
}
}
person
konjac
schedule
26.05.2013
