题解 P4651 【[BalticOI 2005]Maze】

施玮宸SECSA · 2020-01-02 21:19:43 · 题解

第一次在做这道题时：\ whaaaat?什么题目？\ 但是，这题真有那么难吗?????????\ 经过一定思考后，发现该题其实就是一个BFS。此题并没有边权的一定限制，却有一个边的颜色（黑，白，也有可能没有颜色）\ 那么这题是不是一个奇偶最短路（用广度优先搜索来求解）呢？？？？？？ 经过分析，发现的确如此。\ 需要记录走过的边的号码。\ 复杂度：O(ts)~~~

前方贴出代码

#include<bits/stdc++.h>
using namespace std;
const int max_n=1000001,max_m=2000001;
const int max_e=5000001;
struct node{
    int t;
    int w;
    int n;
};//用于链表的结构体
node e[max_e];
bool bl[2][max_n];
int now[max_m],ret[max_m],h[max_m],m;
void a(int x,int y,int z){
    e[++m].w=z;
    e[m].t=y;
    e[m].n=h[x];
    h[x]=m;//链表增边
}
int x,y,xx,yy;
int s,t,u,v;
int le,ri;//左，右
int tmp,rem,res;
char c;//读入的字符
int main(){
    ri=tmp=2;
    cin>>t>>s>>x>>y>>xx>>yy;
    for(int i=1;i<=((s*2)|1);i++){
        c=getchar();//读入
        for(int j=1;j<=((i&1)?t:((t*2)|1));j++){
            c=getchar();//读入
            if('n'==c) continue;
            if((i&1)!=0){
                u=(t+1)*(i/2)+j;
                v=u+1;
            }
            else{
                u=(t+1)*(i/2)+(j/2)+(1&j);
                v=u-(1&j)-t;
            }
            a(v,u,!(c=='w'));
            a(u,v,!(c=='w'));
        }
    }
    //上边是所有的输入&预处理~~~
    now[2]=now[1]=x+1+(t+1)*y;
    ret[1]=0;
    res=0;
    rem=xx+1+(t+1)*yy;
    ret[2]=le=1;
    bl[1][now[1]]=1;
    bl[0][now[1]]=1;
    while(ri>=le){
        if(rem==now[le]){
            break;
        }
        for(int i=h[now[le]];i;i=e[i].n){
            if(e[i].w!=ret[le]){
                v=e[i].t;
                if(bl[e[i].w][v]==0){
                    now[++ri]=v;
                    bl[e[i].w][v]=1;
                    ret[ri]=e[i].w;
                }
            }
        }
        le++;
        if(tmp<le){
            res++;
            tmp=ri;
        }
    }
        //????上面是整个bfs~
    cout<<res<<endl;//最后输出
    return 0;
}

感谢观看。