我没有用双广,用的是紫书上说的把空格提出来重新建了一张图,调试了两天,实在找不出bug,第二组测试数据总是38而不是36。。。
哪位大神做过了这道题,跪求帮助啊!!
链接:http://poj.org/problem?id=3523
ACM一道题 poj3523 UVA1601双向广度优先BFS
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
1条回答 默认 最新
- _forever_ 2015-01-17 06:57关注
#include
#include
#include
#include
using namespace std;const int maxs = 20;
const int maxn = 150; // 75% cells plus 2 fake nodes
const int dx[]= {1,-1,0,0,0}; // 4 moves, plus "no move"
const int dy[]= {0,0,1,-1,0};inline int ID(int a, int b, int c)
{
return (a<<16)|(b<<8)|c;
}int s[3], t[3]; // starting/ending position of each ghost
int deg[maxn], G[maxn][5]; // target cells for each move (including "no move")
inline bool conflict(int a, int b, int a2, int b2)
{
return a2 == b2 || (a2 == b && b2 == a);
}int d[maxn][maxn][maxn]; // distance from starting state
int bfs()
{
queue q;
memset(d, -1, sizeof(d));
q.push(ID(s[0], s[1], s[2])); // starting node
d[s[0]][s[1]][s[2]] = 0;
while(!q.empty())
{
int u = q.front();
q.pop();
int a = (u>>16)&0xff, b = (u>>8)&0xff, c = u&0xff;
if(a == t[0] && b == t[1] && c == t[2]) return d[a][b][c]; // solution found
for(int i = 0; i < deg[a]; i++)
{
int a2 = G[a][i];
for(int j = 0; j < deg[b]; j++)
{
int b2 = G[b][j];
if(conflict(a, b, a2, b2)) continue;
for(int k = 0; k < deg[c]; k++)
{
int c2 = G[c][k];
if(conflict(a, c, a2, c2)) continue;
if(conflict(b, c, b2, c2)) continue;
if(d[a2][b2][c2] != -1) continue;
d[a2][b2][c2] = d[a][b][c]+1;
q.push(ID(a2, b2, c2));
}
}
}
}
return -1;
}int main()
{
int w, h, n;while(scanf("%d%d%d\n", &w, &h, &n) == 3 && n) { char maze[20][20]; for(int i = 0; i < h; i++) fgets(maze[i], 20, stdin); // extract empty cells int cnt, x[maxn], y[maxn], id[maxs][maxs]; // cnt is the number of empty cells cnt = 0; for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) if(maze[i][j] != '#') { x[cnt] = i; y[cnt] = j; id[i][j] = cnt; if(islower(maze[i][j])) s[maze[i][j] - 'a'] = cnt; else if(isupper(maze[i][j])) t[maze[i][j] - 'A'] = cnt; cnt++; } // build a graph of empty cells for(int i = 0; i < cnt; i++) { deg[i] = 0; for(int dir = 0; dir < 5; dir++) { int nx = x[i]+dx[dir], ny = y[i]+dy[dir]; // "Outermost cells of a map are walls" means we don't need to check out-of-bound if(maze[nx][ny] != '#') G[i][deg[i]++] = id[nx][ny]; } } // add fakes nodes so that in each case we have 3 ghosts. this makes the code shorter if(n <= 2) { deg[cnt] = 1; G[cnt][0] = cnt; s[2] = t[2] = cnt++; } if(n <= 1) { deg[cnt] = 1; G[cnt][0] = cnt; s[1] = t[1] = cnt++; } printf("%d\n", bfs()); } return 0;
}
解决 无用评论 打赏 举报
悬赏问题
- ¥15 求daily translation(DT)偏差订正方法的代码
- ¥15 js调用html页面需要隐藏某个按钮
- ¥15 ads仿真结果在圆图上是怎么读数的
- ¥20 Cotex M3的调试和程序执行方式是什么样的?
- ¥20 java项目连接sqlserver时报ssl相关错误
- ¥15 一道python难题3
- ¥15 牛顿斯科特系数表表示
- ¥15 arduino 步进电机
- ¥20 程序进入HardFault_Handler
- ¥15 关于#python#的问题:自动化测试