题解 P1374 【进攻幽暗城】

· · 题解

0.题目大意：

萨尔，小A，恐惧魔王三个人在幽暗城中行动，萨尔和恐惧魔王都会按照指定的方式行动，小A可以自由行动，但是不能离开萨尔s范围外d秒以上。有的格子是障碍无法通行，问小A最快在第几秒抓到恐惧魔王。

N，M<=50的数据很明显是搜索。

1.题目分析

数据范围中1<=答案<=100非常特别，让我们想到了迭代加深搜索，限制搜索的层数，如果搜不到就增加层数。记录限制时长，当前位置，当前时间，已经离开距萨尔s范围的时间。复杂度O（能过） 应该是和bfs差不多的（bfs里每个状态都会被搜到一遍，bfs中没搜到的状态因为层数限制也不会被搜到。

2.实现细节

预处理出萨尔和恐惧魔王在100秒内的行动轨迹卡常是好习惯，注意这两个都有可能怼墙或者出界，特判一下，如果出现这两种情况就让他们不动。

3.各类坑点

题目中最大的坑！读入的x,y坐标是相反的（调了我一个小时）有的数据会有人在墙上的情况出现，对地图中的点的判断要判断map[y][x]而非map[x][y]

还有一些小坑，包括但不限于：

4.代码

还有不懂的细节可以看注释

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int dx[5]={0,0,0,-1,1},dy[5]={0,-1,1,0,0};//移动的状态
const double eps=1e-6;

int len,now,x,y,n,m,s,t,sx,sy,tx,ty,ans,salx[110],saly[110],dlx[110],dly[110];//四个数组分别是萨尔和恐惧魔王的位置
bool map[1010][1010];
char sal[110],dl[110],ss[1010];

int dis(int ax,int ay,int bx,int by){
    return sqrt((ax-bx)*(ax-bx)+(ay-by)*(ay-by))+eps;
}

void dfs(int maxn,int nowx,int nowy,int away,int time){
    if(time>maxn)
        return;//搜索到上界
    if(away>t) return;//人死了
    if(nowx==dlx[time] && nowy==dly[time]) ans=time;//抓到魔王
    for(int i=0;i<=4;i++){
        int x=nowx+dx[i],y=nowy+dy[i];
        if(x<1 || x>m || y<1 || y>n) continue;
        if(map[y][x]) continue;
        dfs(maxn,x,y,dis(x,y,salx[time],saly[time])>s ? away+1 : 0,time+1);
    }
}

int main(){
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i=1;i<=n;i++){
        scanf("%s",ss+1);
        for(int j=1;j<=m;j++)
            map[i][j]=ss[j]-'0';
    }
    scanf("%d%d%d%d",&sy,&sx,&ty,&tx);//大坑
    if(sx==tx && sy==ty){
        printf("0\n");//特判初始位置相同
        return 0;
    }
    scanf("%s%s",sal,dl);
    len=strlen(sal);x=sx;y=sy;now=0;
    sal[0]-='0';
    for(int i=0;i<=110;i++){
        salx[i]=x;
        saly[i]=y;
        x+=dx[sal[now]];
        y+=dy[sal[now]];
        if(map[y][x]){
            x=salx[i];
            y=saly[i];
            now=(now+1)%len;
            sal[now]%='0';
            continue;
        }
        if(x<1 || x>m || y<1 || y>n){
            x=salx[i];
            y=saly[i];
        }//特判撞墙和出界
        now=(now+1)%(len+1);
        if(!now) now+=1;
        sal[now]%='0';
    }//预处理萨尔位置
    len=strlen(dl);x=tx;y=ty;now=0;
    dl[0]-='0';
    for(int i=0;i<=110;i++){
        dlx[i]=x;
        dly[i]=y;
        x+=dx[dl[now]];
        y+=dy[dl[now]];
        if(map[y][x]){
            x=dlx[i];
            y=dly[i];
            now=(now+1)%len;
            dl[now]%='0';
            continue;
        }
        if(x<1 || x>m || y<1 || y>n){
            x=dlx[i];
            y=dly[i];
        }
        now=(now+1)%(len+1);
        if(!now) now++;
        dl[now]%='0';
    }//预处理恐惧魔王的位置
    for(int i=1;i<=100;i++)
        if(!ans) dfs(i,sx,sy,0,0);
    printf("%d\n",ans);
    return 0;
}