欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【算法竞赛入门经典】6.5[图的BFS] 例题6-20 UVa1599 (2)

程序员文章站 2022-06-03 18:29:44
...

【算法竞赛入门经典】7.5 路径寻找问题 例题7-9 UVa1601

之前我写了一个单向BFS+可访问图优化的任务,现在更新一个双向BFS的操作。

双向BFS

双向BFS就是从起点终点同时开始进行BFS,直到找到对方为止。
这样的好处是避免层次过大的情况下,单向BFS过快造成过量数据,导致搜索变满。而双向BFS就很好的优化了这一点。

分析。

注意:双向BFS的情况下,结束的条件变为找到对方!!!!!
这一点由单向BFS改为双向BFS的时候很容易出错。

本题储存结构

与单向BFS时基本相同。只不过不能为了省空间用dis数组是否为-1判断是否访问并且同时储存是否访问了,因为要区别正反的访问标号。
所以,除了原dis数组,需要一个新的vis数组,0表示没访问,1表示正向访问,2表示反向访问。

样例实现代码

#include<iostream>
#include<queue>
#include<cstring>
#define maxs 20
#define maxn 150
using namespace std;
int s[3], d[3];
int nex[maxn], G[maxn][5];
int dx[] = { -1,1,0,0,0 };
int dy[] = { 0,0,-1,1,0 };
int dis[maxn][maxn][maxn];
int vis[maxn][maxn][maxn];
int getID(int a, int b, int c) {
    return ((a << 16) | (b << 8) | c);
}
bool conflict(int a, int b, int a2, int b2) {
    if (a2 == b2 || (a == b2) && (b == a2))
        return true;
    return false;
}
int dfs() {
    memset(dis, 0, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    int pos = getID(s[0], s[1], s[2]);
    int bpos=getID(d[0],d[1],d[2]);
    queue<int>q;
    queue<int>p;
    q.push(pos);
    p.push(bpos);
    dis[s[0]][s[1]][s[2]] = 0;
    dis[d[0]][d[1]][d[2]] = 1;
    while (!q.empty()||p.empty()) {
        int funq=q.size();
        int funp=p.size();
        while(funq--){
            int u = q.front();
            q.pop();
            int a = (u >> 16) & 0xff, b = (u >> 8) & 0xff, c = u & 0xff;
            for (int i = 0; i < nex[a]; i++) {
                int a2 = G[a][i];
                for (int j = 0; j < nex[b]; j++) {
                    int b2 = G[b][j];
                    if (conflict(a, b, a2, b2))
                        continue;
                    for (int k = 0; k < nex[c]; k++) {
                        int c2 = G[c][k];
                        if (conflict(a, c, a2, c2) | conflict(b, c, b2, c2))
                            continue;
                        if (vis[a2][b2][c2]==0) {
                            dis[a2][b2][c2] = dis[a][b][c] + 1;
                            vis[a2][b2][c2] = 1;
                            q.push(getID(a2, b2, c2));
                        }
                        else if(vis[a2][b2][c2]==2)
                            return dis[a][b][c]+dis[a2][b2][c2];
                    }
                }
            }
        }
        while(funp--){
            int u = p.front();
            p.pop();
            int a = (u >> 16) & 0xff, b = (u >> 8) & 0xff, c = u & 0xff;
            for (int i = 0; i < nex[a]; i++) {
                int a2 = G[a][i];
                for (int j = 0; j < nex[b]; j++) {
                    int b2 = G[b][j];
                    if (conflict(a, b, a2, b2))
                        continue;
                    for (int k = 0; k < nex[c]; k++) {
                        int c2 = G[c][k];
                        if (conflict(a, c, a2, c2) | conflict(b, c, b2, c2))
                            continue;
                        if (vis[a2][b2][c2]==0) {
                            dis[a2][b2][c2] = dis[a][b][c] + 1;
                            vis[a2][b2][c2] = 2;
                            p.push(getID(a2, b2, c2));
                        }
                        else if(vis[a2][b2][c2]==1)
                            return dis[a][b][c]+dis[a2][b2][c2];
                    }
                }
            }
        }
    }
    return -1;
}
int main() {
    int w, h, n;
    while (cin >> w >> h >> n) {
        if(n==0)
            break;
        getchar();
        char maze[20][20];
        for (int i = 0; i < h; i++)
            fgets(maze[i], 20, stdin);
        int cnt = 0, x[maxn], y[maxn], ID[maxn][maxn];
        for(int i=0;i<h;i++)
            for(int j=0;j<w;j++)
                if (maze[i][j] != '#') {
                    ID[i][j] = cnt;
                    x[cnt] = i;
                    y[cnt] = j;
                    if (islower(maze[i][j])) {
                        s[maze[i][j] - 'a'] = cnt;
                    }
                    if (isupper(maze[i][j])) {
                        d[maze[i][j] - 'A'] = cnt;
                    }
                    cnt++;
                }
        for (int i = 0; i < cnt; i++) {
            nex[i] = 0;
            int nowx, nowy;
            for (int j = 0; j < 5; j++) {
                nowx = x[i] + dx[j];
                nowy = y[i] + dy[j];
                if (nowx < 0 || nowx >= h || nowy < 0 || nowy >= w)
                    continue;
                if (maze[nowx][nowy] != '#') {
                    G[i][nex[i]] = ID[nowx][nowy];
                    nex[i]++;
                }
            }
        }
        if (n <= 2) {
            nex[cnt] = 1;
            G[cnt][0] = cnt;
            s[2] = d[2] = cnt++;
        }
        if (n <= 1) {
            nex[cnt] = 1;
            G[cnt][0] = cnt;
            s[1] = d[1] = cnt++;
        }
        cout << dfs() << endl;
    }
    return 0;
}

结果

【算法竞赛入门经典】6.5[图的BFS] 例题6-20 UVa1599 (2)
附两种结果比较:
【算法竞赛入门经典】6.5[图的BFS] 例题6-20 UVa1599 (2)