https://stackoverflow.com/questions/16755269
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianBreadth First Search will solve this problem.
Record the status (room, credit) when Karli arrived at room numbered as room with a credit value recorded in credit.
Using a queue to maintain the data. At the beginning, only (outside, 0) is in the queue. Each time, pop the head, and move from the status described by head to each neighbour room of head, then calculate the new status and push them into the end of the queue(remember to use a hash to avoid a same status being added more than once).
When you reach a status (exam, 214), the expand process finishes. The remaining work is to traverse back from the status (exam, 214). When getting a new status in BFS, you can also record the pointer to precursor status.
Here is my code.
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: Sorry I make some mistakes when assigning values to neighbour[]. I hava corrected it.
UPD1: Sorry I forget to check whether credit is 214 when enter the exam room. I hava corrected it.
UPD3: @Nuclearman says that it does not give all the solutions. We only need to remove hash from the code, and calculate the path when generating a new status with credit 214. I give the new code here.
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;
}
}
