最近突然间想怀旧一下热血传奇，于是去淘宝里买了个单机版的热血传奇。在祖玛阁中死了好几次，发现乱走是很消耗人品的事，网络上搜索出来的走法也是无效的，于是只能自己动手了。
打开MirServer\Mir200\Envir\MapInfo.txt文件，找到祖玛阁相关内容，才发现自己小看了这张图。一张图有12个小阁，横4阁，竖3阁；从祖玛六层到祖玛七层有10张祖玛阁的地图——即共120个小地图，手动找一条可行路径是找死的行为。
1.分析一下数据
1.1 截取祖玛阁部分数据：
太长了，放本文的最后。
1.2 使用EXCEL描绘这些坐标，可以得到以下散点图：
1.3 离散化一下数据：
1.3.1 根据数据得知：
一共有10张祖玛阁的地图；
每张地图有12个小阁，纵向3个，横向4个；
每个小阁有4个门，出入口相间±1的坐标值；
1.3.2 将数据离散化到每个小阁（到每个门也行），则共有120个点，每个点包含4个门
#define START_ID 5061 #define END_ID 5071 #define WIDTH 100 #define HEIGHT 100 #define VERTICAL_ROOM 3 #define HORIZONTAL_ROOM 4 #define X_UNIT (WIDTH/HORIZONTAL_ROOM) #define Y_UNIT (HEIGHT/VERTICAL_ROOM) #define DOOR_NUM 4 #define ROOM_NUM (VERTICAL_ROOM*HORIZONTAL_ROOM) #define TOTAL_ROOM_NUM (120+1) #define GET_INDEX(Id,x,y) ((Id-START_ID)*ROOM_NUM + x/X_UNIT*VERTICAL_ROOM + y/Y_UNIT) #define START_INDEX 0 #define END_INDEX 120 struct NodePath { int destRoom; int x; int y; bool flag; }mapNodePath[TOTAL_ROOM_NUM][DOOR_NUM];1.4 从文件读取数据：
注意到有些行中有以‘;’符号开头，根据上下文分析，表示该行是无效数据。因此，读取方式如下：
if(freopen("mapInfo_sub.txt", "r", stdin) == NULL) return 0; int leftID, rightID; int xL, yL; int xR, yR; memset(mapNodePath,0,sizeof(mapNodePath)); memset(map,-1,sizeof(map)); char ch,chL,chR; while(scanf("%c",&ch) != EOF){ if(ch == ';' ){ scanf("%c%d %d %d -> %c%d %d %d ",&chL,&leftID,&xL,&yL,&chR,&rightID,&xR,&yR); continue; } else scanf("%d %d %d -> %c%d %d %d ",&leftID,&xL,&yL,&chR,&rightID,&xR,&yR); int index = GET_INDEX(leftID,xL,yL); for(int i = 0; i < DOOR_NUM; i++){ if(!mapNodePath[index][i].flag){ mapNodePath[index][i].x = xL; mapNodePath[index][i].y = yL; int destRoom = GET_INDEX(rightID,xR,yR); mapNodePath[index][i].destRoom = destRoom; mapNodePath[index][i].flag = true; map[index][destRoom] = 1; break; } } } fclose(stdin);2.1 深度优先搜索
最朴素的想法就是一个个点的去尝试，撞到南墙了就返回来找下一条路。防止一直打转，就需要做些限制。到达某点时，检测一下是否有更短的路径到达该点，有的话就放弃目前路径对该点的搜索——每次到达X点时记下用了几步。
#include #include bool room[TOTAL_ROOM_NUM]; int path[TOTAL_ROOM_NUM]; int depthRoom[TOTAL_ROOM_NUM]; void DeepFindPath(int src, int dest, int depth){ depth++; for(int i = 0; i < DOOR_NUM; i++){ if(mapNodePath[src][i].flag){ int destRoom = mapNodePath[src][i].destRoom; if(depthRoom[destRoom] > depth ){ depthRoom[destRoom] = depth; path[destRoom] = src; if(destRoom == dest) return ; if(room[destRoom]) continue; room[destRoom] = true; DeepFindPath(destRoom, dest, depth); room[destRoom] = false; } } } } void DFS() { memset(depthRoom,0x7f,sizeof(depthRoom)); memset(room,false,sizeof(room)); memset(path,-1,sizeof(path)); room[START_INDEX] = true; depthRoom[START_INDEX] = 0; DeepFindPath(START_INDEX,END_INDEX,0); } 2.2 dijkstra算法
将数据转化一下，用矩阵记录所有小阁的点。这样既可用dijkstra算法解决。网上随便找了个模板，直接套用：
int map[TOTAL_ROOM_NUM][TOTAL_ROOM_NUM]; void dijkstra(){ memset(room,false,sizeof(room)); memset(path,-1,sizeof(path)); int dist[TOTAL_ROOM_NUM]; memset(dist,-1,sizeof(dist)); dist[START_INDEX]=0; while(1) { int v=-1; for(int i=0; i!=TOTAL_ROOM_NUM; ++i) if(!room[i]&&dist[i]>=0) if(v<0||dis
