2 u013044116 u013044116 于 2014.10.01 20:19 提问

ACM一道题 poj3523 UVA1601双向广度优先BFS

我没有用双广,用的是紫书上说的把空格提出来重新建了一张图,调试了两天,实在找不出bug,第二组测试数据总是38而不是36。。。
哪位大神做过了这道题,跪求帮助啊!!
链接:http://poj.org/problem?id=3523

1个回答

lxj1048580178
lxj1048580178   2015.01.17 14: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;

}

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
UVa 1601 - The Morning after Halloween(双向BFS版)
继续上次UVA 1601这道题单向BFS的版本,接下来向双向BFS的方向优化。
uva1601(双向BFS经典题)
题目描述:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=51163 首先用单向BFS解决,代码如下。最后在单向基础上改进成双向单向:/* solution: 还是隐式图搜索问题,类似dijkstra,用bfs解决,这个是单向搜索,弊端是有时候随着搜索 的深入,可扩展的结点会越来越多,造成效率变慢,用双向bfs
所谓的 双向BFS
双向BFS,既然是双向的,那么就得知道起点和终点,这样,我们就可以进行双向搜索了。 但是,双向BFS是否真的可以提高效率呢?如果能,那么又能提高多少呢? 看到过一个图,说双BFS可以在BFS的基础上把时间和空间复杂度上都减半。实际上,在许多的实际应用中,往往不仅仅是减半! 这就是我比较注重双BFS的原因。 我们假设,单向BFS需要搜索N层才能到达终点,在每个层需要进行的判断量(即通常的那个
BFS广度优先搜索(11)--hdu2102(基础题)
A计划 TimeLimit:1000MS    Memory Limit:32768KB    64bit IO Format:%I64d & %I64u Description Input Output
ACM_程序设计竞赛:穷举法:BFS(广度优先)
类似于层次遍历 首先访问起始顶点v, v出发,依次访问领接的顶点w1,w2,...,wiw_1,w_2,...,w_i 不后退,一步可以访问一批结点//结果:abcdefgh //算法: bool visited[MAX_VERTEX_NUM];//访问标记数组 void BFSTraverse(Graph G){ //图G进行广度优先遍历,设访问函数visit() for(i=0
深度优先搜索DFS/广度优先搜索BFS的一个应用实例(华为编程大赛赛题)
#include #include #include #include typedef struct { int x; int y; }MapPos; const int BLOCK = 0; // 0代表此路径不可通过 const int PASS = 1; // 1代表此路径可通过 const int VISITED = 2; // 2代表
训练第二周之BFS算法(广度优先搜索)
本篇参考自rapheal的【算法入门】广度/宽度优先搜索(BFS),觉得写得超级赞,大家去他那里相信会有很多收获。基本简介:每次将集合中的元素经过一些改动,分层生成当前状态的子状态(通常还删除父情况),添加到集合(队列)中,以实现遍历或搜索等目的的算法。一般可以用它做什么呢?一个最直观经典的例子就是走迷宫,我们从起点开始,找出到终点的最短路程,很多最短路径算法就是基于广度优先的思想成立的。据图说明:
广度优先搜索寻找最优路径、以及双向广度搜索算法
这里是poj1915上的一道在棋盘上搜索自由路径的题目:代码如下(使用BFS):/* * 使用BFS寻找最佳路径*/#include#include#includeusing namespace std;#define MAXSIZE 301#define NOT !int size;int startX,startY,endX,endY;int minStep;typedef struct Node{        //node结构体 int x;     int y; int myindex; int
例题7-9 万圣节后的早晨 UVa1601
1.题目描述:点击打开链接 2.解题思路:这道题是稀疏图存储+BFS,只要存储好稀疏图,本题就不难解决,但还是怪自己太年幼,不会写稀疏图,磕磕绊绊自己敲了一天样例还有一个没过==,最后弃疗直接学习大牛们的代码。有很多值得学习的地方,关键位置都标记了注释。 3.代码: #define _CRT_SECURE_NO_WARNINGS #include #include #include #i
双向BFS及优化
单向BFS只从起点一端开始搜索,双向BFS则是从起点和终点两边扩展节点,当节点发生重合时即找到最优解。 假设起点到终点深度为d,每个节点平均有n个分支,那么单向BFS需要扩展的节点个数为。而从起点终点同时扩展,则只需。 实现方法为:维护两个队列,分别保存从起点和终点扩展到的下一层,这样保证了两个队列中的节点处于相同的深度(即:距离起点或者终点深度相同)。则当拓展到时一定发生重合,得到最优解。代