题目地址：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3698

题意自己google翻译。

明显的给出了monster，tower各个属性，这肯定是要建类。

不过要注意的细节是移动方式。

dir[8][2]= {0,1,0,-1,1,0,-1,0,1,1,1,-1,-1,1,-1,-1}

到了搜索路径的时候实际作用的其实是dir[][](0~3).

queue注意是x,y方向搜索。

其他一些判重之类没什么好讲。中等水题，需要的是无尽的耐心和细心。享受孤独，以及TLE剪纸之后WA的心情（笑）fascinating！

AC代码:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<utility>
using namespace std;
#define ll long long
char mm[60][60];
//int dir[8][2]= {0,1,0,-1,1,0,-1,0,1,1,1,-1,-1,1,-1,-1};
int dx[8]={0,0,1,-1,1,1,-1,-1};
int dy[8]={1,-1,0,0,1,-1,1,-1};
int sx,sy,tx,ty,tott,totm,totmm;
int n,m,Hp,tot,to[60][60][2],dis[60][60];
struct monster
{
    int x,y,hp,t;
    bool need,ice;
    void born(int a)
    {
        x=sx;
        y=sy;
        t=a;
        hp=Hp;
        need=ice=0;
    }
    void move()
    {
        if(need)hp-=10;
        if(ice)
        {
            ice=0;
            return;
        }
        int nx=to[x][y][0],ny=to[x][y][1];
        x=nx;
        y=ny;
    }
    friend bool operator < (monster m1,monster m2)
    {
        if(m1.hp>0&&m2.hp>0)
        {
            if(m1.x==m2.x&&m1.y==m2.y)
            {
                return m1.t<m2.t;
            }
            return dis[m1.x][m1.y]<dis[m2.x][m2.y];
        }
        return m1.hp>m2.hp;
    }
} mon[60],tmm[60];
struct tower
{
    int x,y;
    char typ;
    tower(int a,int b,char ty)
    {
        x=a;
        y=b;
        typ=ty;
    }
    tower(){}
    bool in(int mx,int my)
    {
        for(int i=0; i<8; i++)
        {
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(nx==mx&&ny==my)return 1;
        }
        return 0;
    }
    void attack()
    {
        if(typ=='B')
        {
            for(int i=0; i<totm; i++)
                if(in(mon[i].x,mon[i].y))
                {
                    mon[i].hp-=10;
                    break;
                }
        }
        if(typ=='F')
        {
            for(int i=0; i<totm; i++)
                if(in(mon[i].x,mon[i].y))
                {
                    mon[i].hp-=10;
                }
        }
        if(typ=='N')
        {
            for(int i=0; i<totm; i++)
                if(in(mon[i].x,mon[i].y))
                {
                    mon[i].need=1;
                    break;
                }
        }
        if(typ=='I')
        {
            for(int i=0; i<totm; i++)
                if(in(mon[i].x,mon[i].y))
                {
                    mon[i].ice=1;
                    break;
                }
        }
    }
}tow[60];
bool check(int x,int y)
{
    if(!(x>=0&&x<n&&y>=0&&y<m))return 0;
    if(mm[x][y]!='.'&&mm[x][y]!='T'&&mm[x][y]!='S')return 0;
    return 1;
}
void  route()
{
    memset(to,-1,sizeof(to));
    memset(dis,-1,sizeof(dis));
    queue<int>q[2];
    to[tx][ty][0]=tx;
    to[tx][ty][1]=ty;
    dis[tx][ty]=0;
    q[0].push(tx);
    q[1].push(ty);
    while(!q[0].empty())
    {
        int x=q[0].front();
        q[0].pop();
        int y=q[1].front();
        q[1].pop();
        for(int i=0; i<4; i++)
        {
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(!check(nx,ny))continue;
            if(to[nx][ny][0]!=-1)continue;
            to[nx][ny][0]=x;
            to[nx][ny][1]=y;
            dis[nx][ny]=dis[x][y]+1;
            q[0].push(nx);
            q[1].push(ny);
        }
    }
}
void born(int a)
{
    mon[totm++].born(a);
}
void clcmon()
{
    sort(mon,mon+totm);
    for(int i=0; i<totm; i++)
    {
        if(mon[i].hp<=0)
        {
            totm=i;
            break;
        }
    }
}
bool checklose()
{
    for(int i=0; i<totm; i++)
    {
        if(mon[i].x==tx&&mon[i].y==ty)
            return 1;
    }
    return 0;
}
bool move(int now)
{
    for(int i=0; i<totm;i++)mon[i].move();
    if(now<=tot)born(now);
    clcmon();
    return checklose();
}
void attack()
{
    for(int i=0; i<tott; i++)
    {
        tow[i].attack();
    }
}
bool judge(monster m1,monster m2)
{
    if(m1.x!=m2.x)return 0;
    if(m1.y!=m2.y)return 0;
    if(m1.ice!=m2.ice)return 0;
    if(m1.need!=m2.need)return 0;
    if(m1.hp!=m2.hp)return 0;
    return 1;
}
bool same()
{
    if(totmm!=totm)return 0;
    for(int i=0; i<totm;i++)if(!judge(tmm[i],mon[i])) return 0;
    return 1;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>m>>tot>>Hp;
        for(int i=0; i<n; i++)
            cin>>mm[i];
        totm=tott=0;
        for(int i=0; i<n; i++)
            for(int j=0; j<m; j++)
            {
                if(mm[i][j]=='S')
                {
                    sx=i;
                    sy=j;
                }
                else if(mm[i][j]=='T')
                {
                    tx=i;
                    ty=j;
                }
                else if(mm[i][j]=='B')
                {
                    tow[tott++]=tower(i,j,'B');
                }
                else if(mm[i][j]=='F')
                {
                    tow[tott++]=tower(i,j,'F');
                }
                else if(mm[i][j]=='N')
                {
                    tow[tott++]=tower(i,j,'N');
                }
                else if(mm[i][j]=='I')
                {
                    tow[tott++]=tower(i,j,'I');
                }
            }
            route();
            int ans=0;
            while(1)
            {
                ans++;
                if(move(ans))
                {
                    ans=-1;
                    break;
                }
                attack();
                clcmon();
                if(ans>=tot&&totm==0)break;
                if(ans>tot&&same())
                {
                    ans=-1;
                    break;
                }
                for(int i=0;i<totm;i++)
                    tmm[i]=mon[i];
                totmm=totm;
            }
            cout<<ans<<endl;
    }
}