View Code of Problem 1010

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <cmath>
#include <algorithm>
using namespace std;

int v[130][130][130];
int map[130][130][130];

int dx[9] = {0,-1,1,0,0,-1,1,-1,1};//8  上下左右  右上  右下  左上  左下
int dy[9] = {0,0,0,-1,1,1,1,-1,-1};
int n,m,tot;
int cnt;
int tagx,tagy;

bool flag;
struct mon
{
    int state;
    int len;
    int ax[130];
    int ay[130];
}mst[130];

struct node
{
    int x,y,time;
};



void bfs(node t)
{
    queue<node>Q;
    node w,e;

    w=t;
    Q.push(w);

    while(!Q.empty())
    {
        w=Q.front();
        Q.pop();

        if(w.time >= 100) break;
        
        for(int k=0;k<=16;k++)
        {
            e=w;
            e.time = w.time + 1;
            
            if(map[e.time][e.x][e.y]==0)continue;  //么么哒   题目中说怪物先走，首先就判断怪物走完了之后能不能吃到。都吃到了还搞什么啊。
            
            flag=false;
            if(k<=8)  //前9个方向是WALK
            {
                int xx=e.x + dx[k];
                int yy=e.y + dy[k];
                if(xx<=0 || yy<=0 || xx>100 || yy>100)continue;
                if(map[e.time][xx][yy]!=0 && v[e.time][xx][yy]==0)
                {
                    flag=true;
                    e.x=xx;
                    e.y=yy;
                    v[e.time][xx][yy]=1;
                    if(xx==tagx && yy==tagy){printf("%d\n",e.time);return;}
                }
            }
            else//后面就走两步  当做跑
            {
                int xx=e.x + dx[k-8];
                int yy=e.y + dy[k-8];

                int xxx=xx + dx[k-8];
                int yyy=yy + dy[k-8];

                if(xxx <=0 || yyy<=0 || xxx>100 || yyy>100) continue;

                if(map[e.time][xx][yy]!=0 && map[e.time][xxx][yyy]!=0 && v[e.time][xxx][yyy]==0)//要判断走的路上都可以通过
                {
                    flag=true;
                    e.x=xxx;
                    e.y=yyy;
                    v[e.time][xxx][yyy]=1;
                    if(xxx==tagx && yyy==tagy){printf("%d\n",e.time);return;}
                }
            }

            if(flag)
            {
                Q.push(e);
            }
        }
    }
    printf("impossible\n");
}

int main()
{
    int CS=1;
    while(scanf("%d%d",&n,&m)!=EOF && n && m)
    {

        getchar();
        cnt=1;
        node t;
        char ch[130];
        memset(map,0,sizeof(map));
        memset(v,0,sizeof(v));

        for(int i=1;i<=n;i++)
        {
            scanf("%s",ch);   //再也不用getchar()读入了  坑了一天的RE。 再用getchar剁手！作死。
            for(int j=1;j<=m;j++)
            {
                if(ch[j-1]=='#')map[0][i][j]=0;
                else if(ch[j-1]=='.')map[0][i][j]=1;
                else if(ch[j-1]=='t')
                {
                    map[0][i][j]=1;
                    tagx=i;
                    tagy=j;
                }
                else if(ch[j-1]=='p')
                {
                    map[0][i][j]=1;
                    t.x=i;
                    t.y=j;
                    v[0][i][j]=1;
                }
                else if(ch[j-1]=='a')
                {
                    map[0][i][j]=1;
                    mst[cnt++].state=1;
                }
                else if(ch[j-1]=='n')
                {
                    map[0][i][j]=1;
                    mst[cnt++].state=0;
                }
            }
        }

		for(int p=0;p<=102;p++)
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            map[p][i][j]=map[0][i][j];
        }

        scanf("%d",&tot);
        int k;
        for(int i=1;i<=tot;i++)
        {
            scanf("%d",&k);
            mst[i].len=k;
            for(int j=0;j<k;j++)
            scanf("%d%d",&mst[i].ax[j],&mst[i].ay[j]);

            if(!mst[i].state)
            {
				for(int p=0;p<=102;p++)
				{
					map[p][mst[i].ax[p%mst[i].len]][mst[i].ay[p%mst[i].len]]=0;
				}
            }
            else
            {
                for(int p=0;p<=102;p++)
                for(int s=0;s<=8;s++)
                map[p][mst[i].ax[p%mst[i].len]+dx[s]][mst[i].ay[p%mst[i].len]+dy[s]]=0;
            }
        }
        t.time=0;
        if(CS>1)puts("");
        CS++;
        bfs(t);
        //putchar(10);
    }
    return 0;
}