双向广搜

双向广搜

关注
发信
关注(28)粉丝(399)

万圣节后的早晨&&九数码游戏——双向广搜

https://www.luogu.org/problemnew/show/P1778

https://www.luogu.org/problemnew/show/P2578

双向广搜。

有固定起点终点，过程可逆。

有时用于A*估价函数不好用的时候。

万圣节后的早晨

（由于鬼可以同时移动，估价函数不好设计）

优化：

1.预处理。

预处理每个可以到的位置的上下左右的块能否到达，建一个类似前向星的数组。

就可以很快地查询了。

2.每次枚举前1/2个鬼就可以判定当前的状态是否合法，可以减掉不少。

尽可能提前判断合法性，越快越好。

代码：

#include<bits/stdc++.h>

#define ri register int

using namespace std;

typedef long long ll;

const int N=;

const int M=;

const int P=;

int mp[N][N];

int d1[M][M][M];

int d2[M][M][M];

int id[N][N];

int to[M][],sz[M];

int tot;

int n,m,k;

char s[N];

struct node{

    int mem[];

    void clear(){

        mem[]=mem[]=mem[]=mem[]=;

    }

    void op(){

        cout<<mem[]<<" "<<mem[]<<" "<<mem[]<<endl;

    }

}st,nd;

node unzip(ll x){

    //cout<<" unzip "<<x<<endl;

    node ret;

    ret.clear();

    int cnt=;

    while(x){

        cnt++;

        ret.mem[cnt]=x%P;

        x/=P;

    }

    return ret;

}

int mv[][]={{,},{+,},{-,},{,+},{,-}};

int zip(node lp){

    return lp.mem[]*P*P+lp.mem[]*P+lp.mem[];

}

queue<pair<int,int> >q1;

queue<pair<int,int> >q2;

bool bfs1(int dep){

    while(!q1.empty()){

        pair<int,int>now=q1.front();

        if(now.second==dep) return false;

        q1.pop();

        //cout<<" haha "<<endl;

        node kk=unzip(now.first);

        //if(dep<10) kk.op();

        node lp;lp.clear();

        for(int i=;i<=sz[kk.mem[]];i++){

            lp.mem[]=to[kk.mem[]][i];

            for(int j=;j<=sz[kk.mem[]];j++){

                lp.mem[]=to[kk.mem[]][j];

                if(lp.mem[]==lp.mem[]) continue;

                if(lp.mem[]==kk.mem[]&&lp.mem[]==kk.mem[]) continue;

                //cout<<"lp "<<endl;lp.op();

                for(int p=;p<=sz[kk.mem[]];p++){

                    lp.mem[]=to[kk.mem[]][p];

                    if(lp.mem[]){

                        if(lp.mem[]==lp.mem[]) continue;

                        if(lp.mem[]==lp.mem[]) continue;

                        if(lp.mem[]==kk.mem[]&&lp.mem[]==kk.mem[]) continue;

                        if(lp.mem[]==kk.mem[]&&lp.mem[]==kk.mem[]) continue;

                    }

                    if(d2[lp.mem[]][lp.mem[]][lp.mem[]]!=-) return true;

                    else if(d1[lp.mem[]][lp.mem[]][lp.mem[]]==-){

                        d1[lp.mem[]][lp.mem[]][lp.mem[]]=dep;

                        q1.push(make_pair(zip(lp),now.second+));

                    }

                }

            }

        }

    }

    return false;

}

bool bfs2(int dep){

    while(!q2.empty()){

        pair<int,int>now=q2.front();

        if(now.second==dep) return false;

        q2.pop();

        node kk=unzip(now.first);

        node lp;lp.clear();

        for(int i=;i<=sz[kk.mem[]];i++){

            lp.mem[]=to[kk.mem[]][i];

            for(int j=;j<=sz[kk.mem[]];j++){

                lp.mem[]=to[kk.mem[]][j];

                if(lp.mem[]==lp.mem[]) continue;

                if(lp.mem[]==kk.mem[]&&lp.mem[]==kk.mem[]) continue;

                for(int p=;p<=sz[kk.mem[]];p++){

                    lp.mem[]=to[kk.mem[]][p];

                    if(lp.mem[]){

                        if(lp.mem[]==lp.mem[]) continue;

                        if(lp.mem[]==lp.mem[]) continue;

                        if(lp.mem[]==kk.mem[]&&lp.mem[]==kk.mem[]) continue;

                        if(lp.mem[]==kk.mem[]&&lp.mem[]==kk.mem[]) continue;

                    }

                    if(d1[lp.mem[]][lp.mem[]][lp.mem[]]!=-) return true;

                    else if(d2[lp.mem[]][lp.mem[]][lp.mem[]]==-){

                        d2[lp.mem[]][lp.mem[]][lp.mem[]]=dep;

                        q2.push(make_pair(zip(lp),now.second+));

                    }

                }

            }

        }

    }

    return false;

}

void clear(){

    tot=;

    memset(mp,,sizeof mp);

    memset(d1,-,sizeof d1);

    memset(d2,-,sizeof d2);

    memset(id,,sizeof id);

    memset(to,,sizeof to);

    memset(sz,,sizeof sz);

    st.clear();

    nd.clear();

    while(!q1.empty())q1.pop();

    while(!q2.empty())q2.pop();

}

int main(){

    while(){

        cin>>m>>n>>k;

        if(n==&&m==&&k==) break;

        clear();

        char ch;while((ch=getchar())||)if(ch=='\n')break;

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

            int lp=;

            while((s[lp]=getchar())||) if(s[lp++]=='\n')break;

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

                if(s[j-]==' '){

                    mp[i][j]=;

                    id[i][j]=++tot;

                }

                else if(s[j-]=='#'){

                    mp[i][j]=;

                }

                else if(s[j-]>='a'&&s[j-]<='z'){

                    id[i][j]=++tot;

                    st.mem[s[j-]-'a'+]=tot;

                }

                else if(s[j-]>='A'&&s[j-]<='Z'){

                    id[i][j]=++tot;

                    nd.mem[s[j-]-'A'+]=tot;

                }

            }

        }

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

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

                if(!id[i][j]) continue;

                //cout<<i<<" "<<j<<endl;

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

                    int dx=i+mv[p][];

                    int dy=j+mv[p][];

                    if(dx<||dx>n) continue;

                    if(dy<||dy>m) continue;

                    if(mp[dx][dy]) continue;

                    sz[id[i][j]]++;

                    to[id[i][j]][sz[id[i][j]]]=id[dx][dy];

                }

            }

        } //cout<<"after "<<endl;

        id[][]=;

        sz[]++;

        to[][]=;

        //st.op();

        q1.push(make_pair(zip(st),));

        //cout<<zip(st)<<endl;

        d1[st.mem[]][st.mem[]][st.mem[]]=;

        q2.push(make_pair(zip(nd),));

        d2[nd.mem[]][nd.mem[]][nd.mem[]]=;

        int ans=;

        int b1=,b2=;

        while(){

            ans++;

            //if(ans<10) cout<<ans<<endl;

            if(bfs1(++b1)) break;

            ans++;

            if(bfs2(++b2)) break;

        }

        cout<<ans<<endl;

    }

    return ;

}

九数码游戏

（由于顺时针转，变化太大，估价函数也不好设计。）

（当然这个题可以直接bfs，但是双向广搜在luogu上快了50倍）其实要注意的就是一点。

因为双向广搜的另一边是一个逆过程，所以，顺时针变成逆时针，向右变成向左。

值得注意。

至于方案，根据hash表中元素的单一性，而且有SPJ，所以，记录一下每个状态的前驱即可。

代码：

// luogu-judger-enable-o2

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=;

const int M=;

const int mo=1e5;

const int ED=;

struct ha{

    int val[M];

    int nxt[M],hd[mo];

    int pre[M];

    int cnt;

    void ins(int x,int from){

        cnt++;

        val[cnt]=x;pre[cnt]=from;

        int pos=x%mo;

        nxt[cnt]=hd[pos];

        hd[pos]=cnt;

    }

    bool query(int x){

        int pos=x%mo;

        for(int i=hd[pos];i;i=nxt[i]){

            if(val[i]==x) return ;

        }

        return ;

    }

    int fin(int x){

        int pos=x%mo;

        for(int i=hd[pos];i;i=nxt[i]){

            if(val[i]==x) return pre[i];

        }

        return ;

    }

}HA1,HA2;

queue<pair<int,int> >q1;

queue<pair<int,int> >q2;

int st,nd;

int sta[],top;

int num1,num2;

int mp[][];

void op(int x){

    for(int i=;i>=;i--)

        for(int j=;j>=;j--)

            mp[i][j]=x%,x/=;

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

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

            printf("%d ",mp[i][j]);

        }puts("");

    }

    puts("");

}

int mv1(int x){

    for(int i=;i>=;i--)

        for(int j=;j>=;j--)

            mp[i][j]=x%,x/=;

    int tmp=mp[][];

    mp[][]=mp[][];mp[][]=mp[][];mp[][]=mp[][];mp[][]=mp[][];

    mp[][]=mp[][];mp[][]=mp[][];mp[][]=mp[][];mp[][]=tmp;

    int ret=;

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

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

            ret=ret*+mp[i][j];

        }

    }return ret;

}

int mv2(int x){

    for(int i=;i>=;i--)

        for(int j=;j>=;j--)

            mp[i][j]=x%,x/=;

    int tmp=mp[][];

    mp[][]=mp[][];mp[][]=mp[][];mp[][]=tmp;

    int ret=;

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

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

            ret=ret*+mp[i][j];

        }

    }return ret;

}

int mv3(int x){

    for(int i=;i>=;i--)

        for(int j=;j>=;j--)

            mp[i][j]=x%,x/=;

    int tmp=mp[][];

    mp[][]=mp[][];mp[][]=mp[][];mp[][]=mp[][];mp[][]=mp[][];

    mp[][]=mp[][];mp[][]=mp[][];mp[][]=mp[][];mp[][]=tmp;

    int ret=;

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

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

            ret=ret*+mp[i][j];

        }

    }return ret;

}

int mv4(int x){

    for(int i=;i>=;i--)

        for(int j=;j>=;j--)

            mp[i][j]=x%,x/=;

    int tmp=mp[][];

    mp[][]=mp[][];mp[][]=mp[][];mp[][]=tmp;

    int ret=;

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

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

            ret=ret*+mp[i][j];

        }

    }return ret;

}

int bfs1(int dp){

    while(!q1.empty()){

        pair<int,int> lp=q1.front();

        if(lp.second==dp) return ;

        q1.pop();

        int now=lp.first;

        int t1=mv1(now);

        if(HA2.query(t1)){

            num1=now;

            num2=t1;

            return ;

        }

        else if(!HA1.query(t1)){

            HA1.ins(t1,now);

            q1.push(make_pair(t1,lp.second+));

        }

        int t2=mv2(now);

        if(HA2.query(t2)){

            num1=now;

            num2=t2;

            return ;

        }

        else if(!HA1.query(t2)){

            HA1.ins(t2,now);

            q1.push(make_pair(t2,lp.second+));

        }

    }

    return ;

}

int bfs2(int dp){

    while(!q2.empty()){

        pair<int,int> lp=q2.front();

        if(lp.second==dp) return ;

        q2.pop();

        int now=lp.first;

        int t1=mv3(now);

        if(HA1.query(t1)){

            num2=now;

            num1=t1;

            return ;

        }

        else if(!HA2.query(t1)){

            HA2.ins(t1,now);

            q2.push(make_pair(t1,lp.second+));

        }

        int t2=mv4(now);

        if(HA1.query(t2)){

            num2=now;

            num1=t2;

            return ;

        }

        else if(!HA2.query(t2)){

            HA2.ins(t2,now);

            q2.push(make_pair(t2,lp.second+));

        }

    }

    return ;

}

int main(){

    int t;

    for(int i=;i<=;i++)scanf("%d",&t),st=st*+t;

    nd=ED;

    if(st==nd){

        printf("");

        op(st);

    }

    HA2.ins(nd,);

    HA1.ins(st,);

    q1.push(make_pair(st,));

    q2.push(make_pair(nd,));

    int ans=;

    int b1=,b2=;

    while(){

        ans++;

        int d1=bfs1(++b1);

        if(d1==) break;

        ans++;

        int d2=bfs2(++b2);

        if(d2==) break;

        if(d1==&&d2==) {

            printf("UNSOLVABLE");return ;

        }

    }

    //over

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

    top=;

    while(num1!=){

        sta[++top]=num1;

        num1=HA1.fin(num1);

    }

    while(top)op(sta[top--]);

    while(num2!=){

        op(num2);

        num2=HA2.fin(num2);

    }

    return ;

}
05-11 01:13
Powered by LMLPHP ©2024 双向广搜 0.063495