uva 1601 poj 3523 Morning after holloween 万圣节后的早晨（经典搜索，双向bfs+预处理优化+状态压缩位运算）

这题数据大容易TLE

优化：预处理，可以先枚举出5^3的状态然后判断合不合法，但是由于题目说了有很多墙壁，实际上没有那么多要转移的状态那么可以把底图抽出来，然后3个ghost在上面跑到时候就不必判断了，减少了两次无用的枚举。

减少代码的方法：1.结点没有3个时增加冗余点，2.把位置坐标二元组编号成一个数，这点在预处理时可以顺便完成（坐标范围0~15），3.把三个ghost的位置状态压缩成一个数字，方便push，但是注意重时不能直接用Hash掉的值来判断vis，因为Hash以后数字范围很大。

这题为什么不适合Astar。因为Astar的估计用Manhattan距离需要知道坐标，因此不适合把二元组hash成数字，而且不能用一个数来压缩状态了，因为要加上估价值，代码很长，容易写错。

学习点：

1.减少代码量的方法，减少分类，提取不同的问题的相同部分

2.建图的方法。

poj不支持#include<bits/stdc++.h>

//Rey

#include<bits/stdc++.h>

using namespace std;

const int maxw = ;

const int maxn = ;//14*14*3/4+2 149

int s[];

int t[];

int w,h,n;

char maze[maxw][maxw+];

int deg[maxn],G[maxn][];

inline bool conflict(int a1,int b1,int a2,int b2){

    return a1 == a2 || (a1 == b2 && a2 == b1);

}

int vis1[maxn][maxn][maxn];

int vis2[maxn][maxn][maxn];

typedef vector<int> VINT;

VINT v1;

VINT v2;

VINT v3;

typedef VINT * PV;

inline int Hash(int a,int b,int c) {return a<<|b<<|c;}

int dBfs()

{

    v1.clear();v2.clear();v3.clear();

    memset(vis1,-,sizeof(vis1));

    memset(vis2,-,sizeof(vis2));

    PV q1 = &v1,q2 = &v2,nxt = &v3;

    int (*d1)[maxn][maxn] = vis1, (*d2)[maxn][maxn] = vis2;

    d1[s[]][s[]][s[]] = ;

    d2[t[]][t[]][t[]] = ;

    q1->push_back(Hash(s[],s[],s[]));

    q2->push_back(Hash(t[],t[],t[]));

    while(q1->size()&&q2->size()){

        if(q1->size()>q2->size()) swap(q1,q2),swap(d1,d2);

        for(int ii = ,sz = q1->size(); ii < sz; ii++){

            int u = (*q1)[ii];

            int a = u>>, b = (u>>)&0xff, c = u&0xff;

            for(int i = ; i < deg[a]; i++){

                int a1 = G[a][i];

                for(int j = ; j < deg[b]; j++){

                    int b1 = G[b][j];

                    if(conflict(a1,a,b1,b)) continue;

                    for(int k = ; k < deg[c]; k++){

                        int c1 = G[c][k];

                        if(conflict(c1,c,a1,a)||conflict(c1,c,b1,b)||~d1[a1][b1][c1]) continue;

                        d1[a1][b1][c1] = d1[a][b][c]+;

                        if(~d2[a1][b1][c1]) { return d1[a1][b1][c1]+d2[a1][b1][c1]; }

                        nxt->push_back(Hash(a1,b1,c1));

                    }

                }

            }

        }

        q1->clear();

        swap(nxt,q1);

    }

    return -;

}

void init()

{

    int cnt = ;

    int id[maxw][maxw];

    const int dx[] = {-, , , , };

    const int dy[] = { , ,-, , };

    int x[maxn];

    int y[maxn];

    for(int i = ; i < h; i++)

    for(int j = ; j < w; j++) {

        char ch = maze[i][j];

        if(ch != '#'){

            x[cnt] = i; y[cnt] = j;  id[i][j] = cnt;

            if('A'<= ch && ch <= 'C') {t[ch-'A'] = cnt;}

            else if('a' <= ch && ch <= 'c') {s[ch-'a'] = cnt; }

            cnt++;

            }

        }

    for(int i = ; i < cnt; i++){

        deg[i] = ;

         for(int k = ; k < ; k++) {

            int nx = x[i]+dx[k], ny = y[i]+dy[k];

            if(maze[nx][ny] != '#')

                G[i][deg[i]++] = id[nx][ny];

        }

    }

    if(n<=) {deg[cnt] = ; G[cnt][] = cnt; s[] = t[] = cnt++; }

    if(n<=) {deg[cnt] = ; G[cnt][] = cnt; s[] = t[] = cnt++; }

}

int main()

{

    //freopen("in.txt","r",stdin);

    while(~scanf("%d",&w)&&w) {

        scanf("%d%d\n",&h,&n);

        for(int i = ; i < h; i++)

            gets(maze[i]);//G[i-1]

            init();

            int ans = dBfs();

            printf("%d\n",ans);

    }

    return ;

}

巴特西

uva 1601 poj 3523 Morning after holloween 万圣节后的早晨（经典搜索，双向bfs+预处理优化+状态压缩位运算）

最新文章

热门文章

巴特西

uva 1601 poj 3523 Morning after holloween 万圣节后的早晨 （经典搜索，双向bfs+预处理优化+状态压缩位运算）

最新文章

热门文章

uva 1601 poj 3523 Morning after holloween 万圣节后的早晨（经典搜索，双向bfs+预处理优化+状态压缩位运算）