状态空间搜索。。不过状态数量比较多,很容易TLE
优化的方法:
1、压缩状态
因为地图最大16*16,所以可以用0-255来标记每一个格子,很轻松的将二维坐标变为一个整数
2、使用邻接表
如果每次都使用“尝试走一步看看行不行”的方法,会重复很多次无用的判断。所以用一个vector来保存每个空地相邻的空地,每次走路就遍历这个vector
3、判重的方法
一开始我用了State类型的map来判重,速度很慢。而使用整数来标记格子后,可以用一个三维数组(因为最多有三个ghost)进行判重,我自己测试时的速度就由20s提升到了1s
很搞笑的是我用普通bfs和双向bfs的速度差不多,而A*就会TLE(应该是我的启发函数设计的不好,我用的是三个ghost距离目的地的曼哈顿距离和)。
Run Time: 2.909s
#define UVa "LT7-9.1601.cpp" #include<cstring> #include<cstdlib> #include<cstdio> #include<string> #include<vector> #include<queue> using namespace std; //Global Variables. int w, h, n; int m[20][20]; int dst[3][2], startPosition[3][2]; int step[2][5] = {{-1,0,1,0,0},{0,1,0,-1,0}}; vector<int> G[300]; int vis[300][300][300]; ///// struct State { int dist; int g[3]; int prev[3]; State():dist(0){ for(int i = 0; i < n; i ++) g[i] = startPosition[i][0] * w + startPosition[i][1]; } void setprev (const State& prevS){ for(int i = 0; i < n; i ++) prev[i] = prevS.g[i]; } int is_arrived() { for(int i = 0; i < n; i ++) if(g[i] != dst[i][0] * w + dst[i][1]) return 0; return 1; } int collisionexchange() { if(dist == 0) return 0; //starting state. for(int i = 0; i < n; i ++) for(int j = 0; j < n; j ++) if(i != j){ if(g[i] == g[j]) return 1; //collision if(g[i] == prev[j] && prev[i]== g[j]) return 1; //exchange } return 0; //## } bool operator < (const State& s) const { for(int i = 0; i < 3; i ++) { if(g[i] < s.g[i]) return true; if(g[i] > s.g[i]) return false; } return false; } }; void solve() { State start = State(); queue<State> q; q.push(start); while(!q.empty()) { State u = q.front(); q.pop(); if(u.is_arrived()) { printf("%d\n", u.dist); return; } State newS; newS.setprev(u); newS.dist = u.dist + 1; int cur1 = u.g[0]; for(int i = 0; i < G[cur1].size(); i ++) { int new1 = G[cur1][i]; newS.g[0] = new1; if(n >= 2) { int cur2 = u.g[1]; for(int j = 0; j < G[cur2].size(); j ++) { int new2 = G[cur2][j]; newS.g[1] = new2; if(n >= 3) { int cur3 = u.g[2]; for(int k = 0; k < G[cur3].size(); k ++) { int new3 = G[cur3][k]; newS.g[2] = new3; if(!vis[newS.g[0]][newS.g[1]][newS.g[2]] && !newS.collisionexchange()) { vis[newS.g[0]][newS.g[1]][newS.g[2]] = 1; q.push(newS); } } } else if (n == 2) { if(!vis[newS.g[0]][newS.g[1]][0] && !newS.collisionexchange()) { vis[newS.g[0]][newS.g[1]][0] = 1; q.push(newS); } } } } else if (n == 1) { if(!vis[newS.g[0]][0][0] && !newS.collisionexchange()) { vis[newS.g[0]][0][0] = 1; q.push(newS); } } } } } void read_floor() { char ch; int charPos[30]; memset(charPos, -1, sizeof(charPos)); int cnt = 0; for(int i = 0; i < h; i ++) { for(int j = 0; j < w; j ++) { scanf("%c", &ch); if(j == 0) while(ch != '#') { scanf("%c", &ch); } if(ch == '#') m[i][j] = 0; else { m[i][j] = 1; if(isalpha(ch)) { if(isupper(ch)) { if(charPos[ch-'A'] == -1) { dst[cnt][0] = i; dst[cnt][1] = j; charPos[ch-'A'] = cnt; cnt ++; } else { dst[charPos[ch-'A']][0] = i; dst[charPos[ch-'A']][1] = j; } } else { if(charPos[ch-'a'] == -1) { startPosition[cnt][0] = i; startPosition[cnt][1] = j; charPos[ch-'a'] = cnt; cnt ++; } else { startPosition[charPos[ch-'a']][0] = i; startPosition[charPos[ch-'a']][1] = j; } } } } } } } void read_G() { for(int i = 0; i < h; i ++) { for(int j = 0; j < w; j ++) { int cur = i*w + j; if(m[i][j] == 0) continue; vector<int> vec; vec.push_back(cur); G[cur] = vec; for(int k = 0; k < 4; k ++) { int newR = i + step[0][k], newC = j + step[1][k]; if(newR < 0 || newR > h || newC < 0 || newC > w || m[newR][newC] == 0) continue; int tmp = newR * w + newC; G[cur].push_back(tmp); } } } } int main() { while(scanf("%d%d%d", &w,&h,&n) && w && h && n) { memset(dst, -1, sizeof(dst)); memset(startPosition, -1, sizeof(startPosition)); memset(vis, 0, sizeof(vis)); read_floor(); read_G(); solve(); } return 0; }