其实在比赛的时候就想到了，在BFS的时候增加一维时间，也就是本来是在平面上的迷宫现在变成了立体的，每一次BFS的时候都向下一层判断5个格子。
我在比赛的时候想到了增加一维时间。。。最坏情况考虑在原地等待15S，然后从左下角到右上角消耗30S，时间维最多不超过50，但是为了保险起见还是开了100
比赛的时候没写出来，理由是预处理有点难写呀
在每一S都要把对应的陷阱的位置写出来，判断不能出界，出界了要保持在原地。。。。。
赛后写出来了，权当是练手了吧。
#include <iostream> #include <queue> #include <cstring> #include <algorithm> using namespace std; const int dx[]{0,0,0,1,-1},dy[]{0,1,-1,0,0}; struct Node{ int x,y,z; explicit Node(int a=0,int b=0,int c=0):x(a),y(b),z(c){} }node; bool board[20][20][100],flag; int t,r,c,k,pr[20],pc[20],qr[20],qc[20],dr[20],dc[20],res[20][20][100]; void pretreatment(); inline bool judgeInBoard(const Node& a){ return a.x>=0&&a.x<r&&a.y>=0&&a.y<c&&a.z<100; } queue<Node> q; int main(){ ios_base::sync_with_stdio(false); cin>>t; while(t--){ cin>>r>>c>>k; for(int i=0;i<k;++i) cin>>pr[i]>>pc[i]>>qr[i]>>qc[i]>>dr[i]>>dc[i]; pretreatment(); q.push(Node(0,0,0)); while(!q.empty()){ node=q.front(); q.pop(); if(node.x==r-1&&node.y==c-1){ cout<<res[node.x][node.y][node.z]<<endl; flag=true; break; } for(int i=0;i<5;++i) if(judgeInBoard(Node(node.x+dx[i],node.y+dy[i],node.z+1))&&!board[node.x+dx[i]][node.y+dy[i]][node.z+1]&&!res[node.x+dx[i]][node.y+dy[i]][node.z+1]){ res[node.x+dx[i]][node.y+dy[i]][node.z+1]=res[node.x][node.y][node.z]+1; q.push(Node(node.x+dx[i],node.y+dy[i],node.z+1)); } } if(!flag) cout<<-1<<endl; } return 0; } void pretreatment(){ flag=false; while(!q.empty()) q.pop(); memset(res,0,sizeof res); memset(board,0,sizeof board); for(int i=0;i<k;++i){ int time=0; for(;judgeInBoard(Node(pr[i]+time*dr[i],pc[i]+time*dc[i],time))&&judgeInBoard(Node(qr[i]+time*dr[i],qc[i]+time*dc[i],time));++time) for(int ler=pr[i]+time*dr[i],rir=qr[i]+time*dr[i],lec=pc[i]+time*dc[i],ric=qc[i]+time*dc[i];ler<=rir;++ler) for(int tec=lec;tec<=ric;++tec) board[ler][tec][time]=true; --time; for(int ler=pr[i]+time*dr[i],rir=qr[i]+time*dr[i],lec=pc[i]+time*dc[i],ric=qc[i]+time*dc[i],k=time+1;k<100;++k) for(int ter=ler;ter<=rir;++ter) for(int tec=lec;tec<=ric;++tec) board[ter][tec][k]=board[ter][tec][time]; } }