#include <cstdio>
#include <map>
#include <iostream>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <climits>
#define STEP_COST 1000
#define COMMAND_COST 6000
#define INTERROOM_COST 30000
int dx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
struct room
{
room() {}
room(const char* roomdata);
unsigned char blockmap[18][24];
unsigned char trans_N;
unsigned char trans_E;
unsigned char trans_S;
unsigned char trans_W;
unsigned char trans_U;
unsigned char trans_D;
unsigned distmap[18][24];
};
room::room(const char* roomdata)
{
for(unsigned i = 0; i < 432; i++)
blockmap[i / 24][i % 24] = roomdata[i];
for(unsigned j = 0x22D; j < 0x23F; j++) {
unsigned type = roomdata[j];
switch(type) {
case 'N': trans_N = atoi(roomdata + j + 1); break;
case 'E': trans_E = atoi(roomdata + j + 1); break;
case 'S': trans_S = atoi(roomdata + j + 1); break;
case 'W': trans_W = atoi(roomdata + j + 1); break;
case 'U': trans_U = atoi(roomdata + j + 1); break;
case 'D': trans_D = atoi(roomdata + j + 1); break;
};
}
}
struct rooms
{
std::vector<room> rooms;
};
struct position
{
unsigned char r;
unsigned char x;
unsigned char y;
position(const char* spec)
{
x = spec[0] - 'A';
y = spec[1] - 'A';
r = atoi(spec + 2);
}
position() : r(0), x(0), y(0) {}
position(unsigned char _r, unsigned char _x, unsigned char _y) : r(_r), x(_x), y(_y) {}
bool operator==(const position& p) const { return (r == p.r && x == p.x && y == p.y); }
bool operator<(const position& p) const { return (r < p.r || (r == p.r && x < p.x) || (r == p.r && x == p.x &&
y < p.y)); }
position move(struct rooms& rooms, unsigned dir)
{
int _dx, _dy;
unsigned x2, y2;
_dx = dx[dir];
_dy = dy[dir];
if(y == 0 && _dy < 0)
return (rooms.rooms[r].trans_N) ? position(rooms.rooms[r].trans_N, x, 17) : *this;
if(y == 17 && _dy > 0)
return (rooms.rooms[r].trans_S) ? position(rooms.rooms[r].trans_S, x, 0) : *this;
if(x == 0 && _dx < 0)
return (rooms.rooms[r].trans_W) ? position(rooms.rooms[r].trans_W, 23, y) : *this;
if(x == 23 && _dx > 0)
return (rooms.rooms[r].trans_E) ? position(rooms.rooms[r].trans_E, 0, y) : *this;
x2 = x + _dx;
y2 = y + _dy;
if(rooms.rooms[r].blockmap[y2][x2] == 'U')
return (rooms.rooms[r].trans_U) ? position(rooms.rooms[r].trans_U, x, y) : *this;
if(rooms.rooms[r].blockmap[y2][x2] == 'D')
return (rooms.rooms[r].trans_D) ? position(rooms.rooms[r].trans_D, x, y) : *this;
if(rooms.rooms[r].blockmap[y2][x2] == ' ')
return position(r, x2, y2);
else
return *this;
}
};
struct item
{
unsigned char symbol; // for example 's' for SWORD
unsigned int weight; // 1 for objects, 0 for monsters
struct position pos; // room, x, y
unsigned int namelen; // for example 5 for SWORD, longer item names take longer to drop
item() : pos("AA0") {}
item(unsigned char _s, unsigned int _w, struct position _p, unsigned int _l) : symbol(_s), weight(_w),
pos(_p), namelen(_l) {}
};
unsigned search_route(struct rooms& rooms, const position& src, const position& dest)
{
for(unsigned i = 0; i < rooms.rooms.size(); i++)
for(unsigned j = 0; j < 18; j++)
for(unsigned k = 0; k < 24; k++) {
rooms.rooms[i].distmap[j][k] = UINT_MAX;
}
rooms.rooms[src.r].distmap[src.y][src.x] = 0;
std::multimap<unsigned, position> queue;
std::map<position, unsigned> in_queue;
queue.insert(std::make_pair(0U, src));
in_queue[src] = 0;
while(!queue.empty()) {
unsigned cost = rooms.rooms[dest.r].distmap[dest.y][dest.x];
std::multimap<unsigned, position>::iterator i = queue.begin();
unsigned curcost = i->first;
position current = i->second;
queue.erase(i);
in_queue.erase(current);
if(cost < curcost)
return cost;
//std::cerr << "Searching: {" << (int)current.r << ", " << (int)current.x << ", " << (int)current.y
// << "} at cost " << curcost << std::endl;
for(unsigned j = 0; j < 8; j++) {
position newpos = current.move(rooms, j);
if(!(newpos == current)) {
unsigned newcost;
if(newpos.r != current.r)
newcost = curcost + INTERROOM_COST;
else
newcost = curcost + STEP_COST;
if(newcost >= rooms.rooms[newpos.r].distmap[newpos.y][newpos.x])
continue;
rooms.rooms[newpos.r].distmap[newpos.y][newpos.x] = newcost;
if(in_queue.count(newpos)) {
std::multimap<unsigned, position>::iterator j =
queue.equal_range(in_queue[newpos]).first;
while(j != queue.end() && j->first == in_queue[newpos] &&
!(j->second == newpos))
j++;
if(j == queue.end() && j->first == in_queue[newpos]) {
std::cerr << "Error: (" << in_queue[newpos] << ", {" <<
(int)newpos.r << ", " << (int)newpos.x << ", " <<
(int)newpos.y << "}) should be in queue."
<< std::endl;
exit(1);
}
queue.erase(j);
queue.insert(std::make_pair(newcost, newpos));
in_queue[newpos] = newcost;
} else {
queue.insert(std::make_pair(newcost, newpos));
in_queue[newpos] = newcost;
}
}
}
}
return rooms.rooms[dest.r].distmap[dest.y][dest.x];
}
struct rooms read_rooms(FILE* in)
{
struct rooms r;
char buffer[575];
r.rooms.push_back(room());
while(fread(buffer, 575, 1, in)) {
struct room rr(buffer);
r.rooms.push_back(rr);
}
r.rooms[67].blockmap[8][18] = r.rooms[67].blockmap[8][19] = ' ';
r.rooms[67].blockmap[9][18] = r.rooms[67].blockmap[9][19] = ' ';
r.rooms[67].blockmap[7][20] = r.rooms[67].blockmap[10][20] = 'X';
r.rooms[67].blockmap[7][21] = r.rooms[67].blockmap[10][21] = 'X';
r.rooms[67].blockmap[7][22] = r.rooms[67].blockmap[10][22] = 'X';
r.rooms[67].blockmap[7][23] = r.rooms[67].blockmap[10][23] = 'X';
r.rooms[77].blockmap[17][11] = r.rooms[77].blockmap[17][12] = ' ';
r.rooms[1].blockmap[17][11] = ' ';
return r;
}
void makelink_item(std::map<char, item>& m, const item& i)
{
m[i.symbol] = i;
}
int main(int argc, char** argv)
{
FILE* rdata = fopen("CASTLE.RAN", "rb");
struct rooms r = read_rooms(rdata);
std::map<char, item> m;
makelink_item(m, item('1', 0, "QN17", 0));
makelink_item(m, item('2', 0, "LL21", 0));
makelink_item(m, item('3', 0, "MI4", 0));
makelink_item(m, item('4', 0, "FJ24", 0));
makelink_item(m, item('5', 0, "MG14", 0));
makelink_item(m, item('6', 0, "RG68", 0));
makelink_item(m, item('7', 0, "QE70", 0));
makelink_item(m, item('8', 0, "RN73", 0));
makelink_item(m, item('F', 1, "FN8", 6));
makelink_item(m, item('C', 1, "IE14", 5));
makelink_item(m, item('G', 1, "JI18", 3)); //must use GET, several positions possible
makelink_item(m, item('O', 1, "FN20", 9));
makelink_item(m, item('R', 1, "DP60", 5));
makelink_item(m, item('T', 1, "LM37", 5));
makelink_item(m, item('N', 1, "LG19", 8)); //must use GET, several positions possible
makelink_item(m, item('S', 1, "GH26", 4));
makelink_item(m, item('H', 1, "PH65", 4));
makelink_item(m, item('J', 1, "MJ29", 8));
makelink_item(m, item('D', 1, "MJ57", 7));
makelink_item(m, item('B', 1, "WN74", 7));
makelink_item(m, item('E', 1, "LJ83", 7));
makelink_item(m, item('s', 1, "KF12", 5));
makelink_item(m, item('k', 1, "IH56", 3)); //must use GET, several positions possible
makelink_item(m, item('l', 1, "SN17", 4));
makelink_item(m, item('w', 1, "DI24", 4));
makelink_item(m, item('d', 0, "LC1", 0)); //approximately, dropoff position will vary
makelink_item(m, item('X', 0, "LR1", 0));
makelink_item(m, item('x', 0, "OO1", 0));
unsigned total_cost = 0;
if(argc == 2) {
for(int i = 0; i < strlen(argv[1]) - 1; i++) {
struct position start(m[argv[1][i]].pos);
struct position end(m[argv[1][i + 1]].pos);
unsigned cost = search_route(r, start, end);
if(cost == UINT_MAX)
total_cost = UINT_MAX;
else
total_cost += cost;
}
} else {
size_t colon;
std::string input;
std::string dest;
std::string drops;
struct position start;
struct position end(m[argv[1][0]].pos);
for(int i = 2; i < argc; i++) {
start = end;
input = argv[i];
colon = input.find_first_of(":");
if (colon != std::string::npos) { //if input string contains ":" then
//split it, first part is destination, second part is list of items to drop
dest = input.substr(0, colon);
drops = input.substr(colon+1);
} else {
dest = input;
drops = "";
}
//to see if it splits correctly
//std::cout << dest << std::endl;
//std::cout << drops << std::endl;
if (dest.length() > 1) { //if long format such as "HH18"...
end = position(dest.c_str());
} else { //if short format "G"
end = position(m[dest.c_str()[0]].pos);
}
//struct position start(argv[i]);
//struct position end(argv[i + 1]);
unsigned cost = search_route(r, start, end);
if(cost == UINT_MAX)
total_cost = UINT_MAX;
else
total_cost += cost;
//calculate cost to drop items
if (drops.length() > 0) {
for(int j = 0; j < drops.length(); j++) {
unsigned dropcost = STEP_COST * (5 + m[drops.c_str()[j]].namelen + 1); //"DROP " and "ITEM" and enter.
total_cost += (dropcost + COMMAND_COST);
}
}
}
}
if(total_cost < UINT_MAX)
std::cout << total_cost << std::endl;
else
std::cout << "No path" << std::endl;
}
//x H R D k T J d:HRDkTJ s 1 l G 5 C KI7:l S 4 w O d:SOCG KI7 N 2 E:w 8 B 7 6:k F 3 X