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

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

• 算法竞赛入门经典75 路径寻找问题 例题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;
}

结果

附两种结果比较：