森林冰火人

· · 个人记录

题目链接

一场没有大模拟的比赛，是不完整的。

——沃·兹基硕德

其实只是一道 bfs（广度优先搜索） 的板子。由于 n\times m 只到了 2000 ，可以直接写 O((n\times m)^2) 的。

即：以一个四元组 (xi,yi,xf,yf) 表示状态：冰人与火人分别在 (xi,yi) 与 (xf,yf) 处。记录这个的最小步数，就和普通的 bfs 一样了。

细节上的处理：

  1. 坐标映射：将坐标 (x,y) 编号为 (x-1)\times m+y 。这样坐标与编号一一对应，有利于后面处理。

  2. 四元组的存法：可以把四元组用结构体存储，并一一对应地映射到一个整数上。承上面一点，记坐标的编号为 \text{id}(x,y) ,则四元组编号表示为 \text{id}(xi,yi)\times n\times m+\text{id}(xf,yf)，同样实现了四元组与编号一一对应。好处是可以把四元组信息（路程等）直接存在一维数组里。

  3. 方向数组：扩展路径用的方向数组可以开 8 个，表示一步可选冰人或火人，各有四种走法。

下面是代码：


const int N=2e3+10,M=(1<<13)+10,inf=1e9,P=1e9+7;
const LL lnf=1e16;

int n,m;

int ci,cf;
int six,siy,sfx,sfy;
char a[N][N];           //地图

struct Pos{int x,y;};
bool operator != (Pos p1,Pos p2){return (p1.x!=p2.x)||(p1.y!=p2.y);}
Pos mt[N];                // 若 (x,y) 为障碍，那么它和哪个机关对应
int dis[N*N];             // 四元组状态映射到一位数组，存最小步数

int id(int x,int y){return (x-1)*m+y;}
int id(Pos p){return (p.x-1)*m+p.y;}

bool chk(Pos p){   //  在图内且非"墙"
    if(p.x<=0||p.x>n||p.y<=0||p.y>m||a[p.x][p.y]=='#')return 0;
    return 1;
}

#define Pr pair<Pos,Pos>   // 两个坐标对表示四元组
#define fi first
#define se second
int id(Pr p){return id(p.fi)*n*m+id(p.se);}  //连续三次定义 id() 了，但是每次传参不同，不冲突
queue<Pr>q;

int gix[8]={0,0,0,0,1,0,-1,0},giy[8]={0,0,0,0,0,1,0,-1};
int gfx[8]={1,0,-1,0,0,0,0,0},gfy[8]={0,1,0,-1,0,0,0,0};

Pr add(Pr p,int i){  // 给一个四元组 "加" 上 i 号 "变换 " ，即走一步
    return mp(((Pos){p.fi.x+gix[i],p.fi.y+giy[i]}),((Pos){p.se.x+gfx[i],p.se.y+gfy[i]}));
}

int bfs(){
    Pr S=mp(((Pos){six,siy}),((Pos){sfx,sfy}));
    memb(dis);
    dis[id(S)]=0;q.push(S);
    while(q.size()){
        Pr u=q.front();q.pop();
        For(i,0,7){
            Pr v=add(u,i);
            if((!chk(v.fi))||(!chk(v.se)))continue;

            if(a[v.fi.x][v.fi.y]=='('&&(v.se!=mt[id(v.fi)]))continue;   // 如果冰人在障碍上，且火人不在对应的机关上

            if(a[v.se.x][v.se.y]=='['&&(v.fi!=mt[id(v.se)]))continue;   // 同上

            if(!ckmin(dis[id(v)],dis[id(u)]+1))continue;

            q.push(v);

            if(a[v.fi.x][v.fi.y]=='I'&&a[v.se.x][v.se.y]=='F')return dis[id(v)];
        }
    }return -1;
}

int main(){
    srand(time(0));
    //freopen("icefire10.in","r",stdin);
    //freopen("icefire10.out","w",stdout);
    n=read();m=read();
    For(i,1,n)scanf("%s",a[i]+1);
    For(i,1,n)For(j,1,m){
        if(a[i][j]=='(')ci++;
        if(a[i][j]=='[')cf++;
        if(a[i][j]=='i')six=i,siy=j;
        if(a[i][j]=='f')sfx=i,sfy=j;
    }
    For(i,1,ci){int x=read(),y=read(),X=read(),Y=read();mt[id(x,y)]=(Pos){X,Y};}
    For(i,1,cf){int x=read(),y=read(),X=read(),Y=read();mt[id(x,y)]=(Pos){X,Y};}

    write(bfs());
}

部分分解释：

  2. 没有冰障碍，火障碍，冰火人独立，分别 bfs 即可。
  3. 地图随机生成，有极大概率根本不需要考虑冰障碍与火障碍，同上。