链接 1829: Dungeon 题意：给一个15*15的迷宫，有20个矩形圈定的区域是不能走 的，同时矩形会匀速运动或者静止，矩形遇到边界后不再移 动。人每次可以往四个方向移动或者静止，问逃出迷宫的最 小步数 分析：由于迷宫范围很小（15*15）， 所以可以判断出至多15s之后，所 有的矩形都将静止。 在可能的逃出的前提下，最差情况是矩形静止后，人物把所有格 子都走一遍（其实这种情况不存在，因为矩形也是要占空间的）， 所以可以推出答案不会超过15*15+15（实际上比这还小得多）， 其实200的步数就足够了而对于一个静止的迷宫，只需要知道哪些位置不能走就行了 定义danger[i][j][k]表示第k秒(i,j)这个位置是否安全暴力递推每一秒每一个矩形的位置，来更新danger[i][j][k]， 然后bfs ，能更新到终点的最小的k即答案。 代码：
#include<iostream> #include<string> #include<cstdio> #include<cstring> #include<vector> #include<math.h> #include<map> #include<queue> #include<algorithm> using namespace std; const int inf = 0x3f3f3f3f; using namespace std; typedef long long LL; typedef pair<int,int> pii; const int N = 18; const int M = 205; const int INF = 0x3f3f3f3f; struct node{ int lx,ly,rx,ry,dx,dy; void read(){ scanf("%d%d%d%d%d%d",&lx,&ly,&rx,&ry,&dx,&dy); } }rec[N][M],base; int T,n,m,k; int dx[5]={0,0,1,-1,0}; int dy[5]={-1,1,0,0,0}; int danger[N][N][M]; int vis[N][N][M]; bool check(int x,int y,int t){//判断是否在矩形内且步数没有超 return x>=0&&x<n&&y>=0&&y<m&&t<M; } bool In(int x,int y){//判断是否在矩形范围内 return x>=0&&x<n&&y>=0&&y<m; } struct Node{ int x,y,t; }; queue<Node> q; int bfs(){ while(!q.empty()) q.pop(); memset(vis,0,sizeof(vis)); q.push((Node){0,0,0}); while(!q.empty()){ Node u=q.front();q.pop(); for(int i=0;i<5;i++){//5个方向 int nx=dx[i]+u.x; int ny=dy[i]+u.y; //判断是否在范围内且步数没有超且当前的格子是否是安全的 if(!check(nx,ny,u.t+1)||danger[nx][ny][u.t+1]||vis[nx][ny][u.t+1]) continue; vis[nx][ny][u.t+1]=u.t+1; q.push((Node){nx,ny,u.t+1}); } } //遍历一下找出最小的时间 for(int i=0;i<M;i++) if(vis[n-1][m-1][i]) return i; return -1; } int main(){ scanf("%d",&T); while(T--){ scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=k;i++){ rec[i][0].read(); node &u=rec[i][0]; for(int j=1;j<M;j++){//判断第i个矩形在第j秒的情况 int lx=u.lx+j*u.dx; int ly=u.ly+j*u.dy; int rx=u.rx+j*u.dx; int ry=u.ry+j*u.dy; //如果已经越界了，则当前的情况为上一秒的情况 if(!In(lx,ly)||!In(lx,ry)||!In(rx,ly)||!In(rx,ry)) rec[i][j]=rec[i][j-1]; else rec[i][j]=(node){lx,ly,rx,ry,u.dx,u.dy}; } } memset(danger,0,sizeof(danger)); for(int i=1;i<M;i++)//在每一秒 for(int j=1;j<=k;j++)//在第j个矩形 for(int t=rec[j][i].lx;t<=rec[j][i].rx;t++)//在第j个矩形中的第i秒中哪些范围是危险的 for(int p=rec[j][i].ly;p<=rec[j][i].ry;p++) danger[t][p][i]=1;//将危险的点置为1 printf("%d\n",bfs()); } return 0; }