#include #include #include using namespace std; unsigned char weights[22*22][22*22]; int rows, cols; bool DEBUG = false; void NodeToPos(int node, int & x, int & y) { x = node /cols; y = node % cols; return; } int PosToNode(int x, int y) { return x*cols+y; } void ReadEastWest(int r) { int c; unsigned char speed; char dir; for(c=0;c> speed >> dir; switch(dir) { case '>': // note I will be going from (r,c) to (r,c+1) weights[PosToNode(r,c)][PosToNode(r,c+1) ] = speed; break; case '<': // note I will be going from (r,c+1) to (r,c) weights[PosToNode(r,c+1)][PosToNode(r,c) ] = speed; break; case '*': // both ways. weights[PosToNode(r,c+1)][PosToNode(r,c) ] = speed; weights[PosToNode(r,c)][PosToNode(r,c+1) ] = speed; break; } } return; } void ReadNorthSouth(int r) { int c; unsigned char speed; char dir; for (c=0;c> speed >> dir; switch(dir) { case 'v': // I will be going from (r,c) to (r+c,c) weights[PosToNode(r,c)][PosToNode(r+1,c) ] = speed; break; case '^': // only from (r+1,c) to (r,c) weights[PosToNode(r+1,c)][PosToNode(r,c) ] = speed; break; case '*': // both weights[PosToNode(r,c)][PosToNode(r+1,c) ] = speed; weights[PosToNode(r+1,c)][PosToNode(r,c) ] = speed; break; } } } void ReadGraph() { int r=0; int east = rows-1; for(r = 0; r <= east;r++) { ReadEastWest(r); if (r < east) { ReadNorthSouth(r); } } return; } void PrintEdge() { int v1, v2; if (DEBUG) { cout << " "; for(v1=0;v1 & nodes, vector & active) { int tmp; int last = active.size()-1; for (int i=0;i active; vector nodes(rows*cols); int current; int next; nodes[0].price = 0; nodes[0].state = ACTIVE; active.push_back(0); while (active.size() > 0 and nodes[rows*cols-1].state != DONE) { // extract the min; MoveMin(nodes, active); current = active.back(); active.pop_back(); nodes[current].state = DONE; for (next =0; next < rows*cols; next++) { if (weights[current][next] > '0' and nodes[next].state != DONE) { int price = 2520/int(weights[current][next]-'0'); if (nodes[next].price > nodes[current].price + price) { nodes[next].price = nodes[current].price + price; } if (nodes[next].state == UNEXPLORED) { nodes[next].state = ACTIVE; active.push_back(next); } } } } return nodes[rows*cols-1].price; } int main() { int east,south; int cost; cin >> south >> east; while (east!=0 and south!=0 ) { Reset(east,south); ReadGraph(); PrintEdge(); cost = Dijkstra(); if (cost < INFIN) { cout << cost << " blips" << endl; } else { cout << "Holiday" << endl; } cin >> south >> east; } return 0; }