tzoj：3613 突破包围

http://www.tzcoder.cn/acmhome/problemdetail.do?&method=showdetail&id=3613

算出两两之间min距离，然后从起点开始循环时间点，到的了的地方进队

#include<bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define pai pair<int,int>

char mp[105][105];

struct node{

    int x,y,ii;

}e,s;

int m,n,k;

vector<node>ve;

vector<pai>v[100105];

int visit[105][105],stp[105][105],kk[105];

int xi[]={1,-1,0,0};

int yi[]={0,0,1,-1};

int solve(node a,node b)//算出两点间最短距离

{

    memset(visit,0,sizeof visit);

    visit[a.x][a.y]=1;

    memset(stp,INF,sizeof stp);

    stp[a.x][a.y]=0;

    queue<node>qu;

    qu.push(a);

    while(!qu.empty()){

        node q=qu.front();qu.pop();

        if(q.x==b.x&&q.y==b.y)return stp[q.x][q.y];

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

            int xx=xi[i]+q.x,yy=yi[i]+q.y;

            if(xx>=0&&xx<n&&yy>=0&&yy<m&&visit[xx][yy]==0&&mp[xx][yy]!='x'){

                visit[xx][yy]=1;

                node p;p.x=xx,p.y=yy;

                stp[p.x][p.y]=stp[q.x][q.y]+1;

                qu.push(p);

            }

        }

    }

    return INF;

}

int solve2(node a,node b)//按时间点进队，看是否能走到终点

{

    int i,j;

    memset(visit,0,sizeof visit);

    visit[a.x][a.y]=1;

    queue<node>qu;

    a.ii=0;//这里注意先赋值再进队！！这点wa了

    qu.push(a);

    i=1;

    while(!qu.empty()){

        while(!qu.empty()&&qu.front().ii+1==i){

            node p=qu.front();qu.pop();

            if(p.x==b.x&&p.y==b.y)return 1;

            for(j=0;j<v[p.x*1000+p.y].size();j++){

                int xi=v[p.x*1000+p.y][j].first,yi=v[p.x*1000+p.y][j].second;

                int xx=xi/1000,xy=xi%1000;

                if(yi<=kk[i]&&visit[xx][xy]==0){

                    visit[xx][xy]=1;

                    node op;op.x=xx,op.y=xy,op.ii=p.ii+1;

                    if(op.x==b.x&&op.y==b.y)return 1;

                    qu.push(op);

                }

            }

            p.ii++;

            qu.push(p);

        }//一个时间点循环一段

        i++;

        if(i>k)return 0;

    }

    return 0;

}

int main()

{

    int i,j,t;scanf("%d",&t);

    while(t--){

        scanf("%d%d",&n,&m);

        ve.clear();

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

            scanf("%s",mp[i]);

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

                if(mp[i][j]=='y')s.x=i,s.y=j,ve.push_back(s);

                if(mp[i][j]=='d')e.x=i,e.y=j,ve.push_back(e);

                if(mp[i][j]=='*'){

                    node oo;oo.x=i,oo.y=j;ve.push_back(oo);

                }

            }

        }

        scanf("%d",&k);

        for(i=1;i<=k;i++)scanf("%d",&kk[i]);

        for(i=0;i<100105;i++)v[i].clear();//这里不要=100105，！！这也wa了！

        for(i=0;i<ve.size();i++){

            for(j=i+1;j<ve.size();j++){

                int dis=solve(ve[i],ve[j]);

                int a=ve[i].x*1000+ve[i].y,b=ve[j].x*1000+ve[j].y;

                v[a].push_back(pai(b,dis));

                v[b].push_back(pai(a,dis));

            }

        }

        int f=solve2(s,e);

        if(f==1)printf("good luck!\n");

        else printf("poor yzq!\n");

    }

}

tzoj：3613 突破包围的相关教程结束。