现在有一个n*m的地图

你在(a,b),你要走到(c,d)

路途中有一堆怪兽= =它们会横竖发射一种可怕的激光..

你碰到激光就死啦..

当你到达(c,d)的那一个瞬间,你可以立即获得一种超能力并且把怪兽全部打死,所以就是说当你到(c,d)的那一步无视激光(甚至碰到怪兽都没关系吧)

每个怪兽是会动的!

实际上,对于每个怪兽都有一条长度为k的路径,它会从第一个点走到最后一个点再走回来这样(k<=7),各个k可以不同

求最少多长时间能到终点

这题和一道"众所周知,榔头可以砸死太极"是一样的..

把每个点拆成120个点..每个点代表在第i秒的时候..你在这个点

然后bfs..

代码有点不太好看..

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
char a[125][65][65];
int dis[125][65][65];
int main()
{
    #ifdef absi2011
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif
    int n,m;
    scanf("%d%d",&n,&m);
    int i;
    int sx,sy,ex,ey;
    scanf("\n(%d %d)",&sx,&sy);
    sx--;
    sy--;
    scanf(" (%d %d)",&ex,&ey);
    ex--;
    ey--;
    for (i=0;i<n;i++)
    {
        scanf("%s",a[0][i]);
    }
    for (i=1;i<120;i++)
    {
        memcpy(a[i],a[0],sizeof(a[i]));
    }
    memset(dis,-1,sizeof(dis));
    int q;
    scanf("%d",&q);
    for (i=0;i<q;i++)
    {
        int k;
        scanf("%d",&k);
        int j;
        for (j=0;j<k;j++)
        {
            int x,y;
            scanf(" (%d %d)",&x,&y);
            x--;
            y--;
            int l;
            if (k==1)
            {
                for (l=j;l<120;l++)
                {
                    int tx=x;
                    int ty=y;
                    for (;;)
                    {
                        if (tx<0) break;
                        if (a[l][tx][ty]=='#') break;
                        a[l][tx][ty]='x';
                        tx--;
                    }
                    tx=x;
                    for (;;)
                    {
                        if (tx>=n) break;
                        if (a[l][tx][ty]=='#') break;
                        a[l][tx][ty]='x';
                        tx++;
                    }
                    tx=x;
                    for (;;)
                    {
                        if (ty<0) break;
                        if (a[l][tx][ty]=='#') break;
                        a[l][tx][ty]='x';
                        ty--;
                    }
                    ty=y;
                    for (;;)
                    {
                        if (ty>=m) break;
                        if (a[l][tx][ty]=='#') break;
                        a[l][tx][ty]='x';
                        ty++;
                    }
                }
                continue;
            }
            for (l=j;l<120;l+=k+k-2)
            {
                int tx=x;
                int ty=y;
                for (;;)
                {
                    if (tx<0) break;
                    if (a[l][tx][ty]=='#') break;
                    a[l][tx][ty]='x';
                    tx--;
                }
                tx=x;
                for (;;)
                {
                    if (tx>=n) break;
                    if (a[l][tx][ty]=='#') break;
                    a[l][tx][ty]='x';
                    tx++;
                }
                tx=x;
                for (;;)
                {
                    if (ty<0) break;
                    if (a[l][tx][ty]=='#') break;
                    a[l][tx][ty]='x';
                    ty--;
                }
                ty=y;
                for (;;)
                {
                    if (ty>=m) break;
                    if (a[l][tx][ty]=='#') break;
                    a[l][tx][ty]='x';
                    ty++;
                }
            }
            if ((j==0)||(j==k-1)) continue;
            for (l=k+k-j-2;l<120;l+=k+k-2)
            {
                int tx=x;
                int ty=y;
                for (;;)
                {
                    if (tx<0) break;
                    if (a[l][tx][ty]=='#') break;
                    a[l][tx][ty]='x';
                    tx--;
                }
                tx=x;
                for (;;)
                {
                    if (tx>=n) break;
                    if (a[l][tx][ty]=='#') break;
                    a[l][tx][ty]='x';
                    tx++;
                }
                tx=x;
                for (;;)
                {
                    if (ty<0) break;
                    if (a[l][tx][ty]=='#') break;
                    a[l][tx][ty]='x';
                    ty--;
                }
                ty=y;
                for (;;)
                {
                    if (ty>=m) break;
                    if (a[l][tx][ty]=='#') break;
                    a[l][tx][ty]='x';
                    ty++;
                }
            }
        }
    }
    for (i=0;i<420;i++)
    {
        a[i][ex][ey]='.';
    }
    static int quex[3200005];
    static int quey[3200005];
    static int quet[3200005];
    int front=0,rail=1;
    quex[0]=sx;
    quey[0]=sy;
    quet[0]=0;
    dis[0][sx][sy]=0;
    for (;front<rail;front++)
    {
        int tx=quex[front];
        int ty=quey[front];
        int ti=quet[front];
        int res=dis[ti][tx][ty];
        ti++;
        if (ti==120) ti=0;
        if ((a[ti][tx][ty]=='.')&&(dis[ti][tx][ty]==-1))
        {
            dis[ti][tx][ty]=res+1;
            quex[rail]=tx;
            quey[rail]=ty;
            quet[rail]=ti;
            rail++;
        }
        if ((tx<n-1)&&(a[ti][tx+1][ty]=='.')&&(dis[ti][tx+1][ty]==-1))
        {
            dis[ti][tx+1][ty]=res+1;
            quex[rail]=tx+1;
            quey[rail]=ty;
            quet[rail]=ti;
            rail++;
        }
        if ((ty<m-1)&&(a[ti][tx][ty+1]=='.')&&(dis[ti][tx][ty+1]==-1))
        {
            dis[ti][tx][ty+1]=res+1;
            quex[rail]=tx;
            quey[rail]=ty+1;
            quet[rail]=ti;
            rail++;
        }
        if ((tx>0)&&(a[ti][tx-1][ty]=='.')&&(dis[ti][tx-1][ty]==-1))
        {
            dis[ti][tx-1][ty]=res+1;
            quex[rail]=tx-1;
            quey[rail]=ty;
            quet[rail]=ti;
            rail++;
        }
        if ((ty>0)&&(a[ti][tx][ty-1]=='.')&&(dis[ti][tx][ty-1]==-1))
        {
            dis[ti][tx][ty-1]=res+1;
            quex[rail]=tx;
            quey[rail]=ty-1;
            quet[rail]=ti;
            rail++;
        }
    }
    int min_ans=-1;
    for (i=0;i<120;i++)
    {
        if (dis[i][ex][ey]==-1) continue;
        if ((dis[i][ex][ey]<min_ans)||(min_ans==-1))
        {
            min_ans=dis[i][ex][ey];
        }
    }
    if (min_ans==-1)
    {
        printf("IMPOSSIBLE");
    }
    else
    {
        printf("%d\n",min_ans);
    }
    return 0;
}