codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#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
Private
[
?
]
Run code
Submit