bfs，首先记录危险方格的时间，因为100时间之后，所有方格均不危险，所以最短时间的最大值为300，记录每个坐标每个时间的状态，直接bfs即可。
#include<cstdio> #include<iostream> #include<queue> using namespace std; struct point{ int x,y,time; }start; int vis[105][105][305] = {0},a[105][105][2] = {0},dir[][2] = {{-1,0},{1,0},{0,-1},{0,1}}; int main() { int n,m,t; scanf("%d%d%d",&n,&m,&t); while(t--) { int x,y,start,stop; scanf("%d%d%d%d",&x,&y,&start,&stop); a[x][y][0] = start; a[x][y][1] = stop; } start.x = 1; start.y = 1; start.time = 0; queue<point> q; q.push(start); while(!q.empty()) { int x = q.front().x,y = q.front().y,time = q.front().time; if(x == n && y == m) { printf("%d ",time); return 0; } q.pop(); for(int i = 0;i < 4;i++) { int xx = x+dir[i][0],yy = y+dir[i][1],timee = time+1; if(xx < 1 || xx > n || yy < 1 || yy > m || timee>=a[xx][yy][0]&&timee<=a[xx][yy][1] || vis[xx][yy][timee]) continue; point temp; temp.x = xx; temp.y = yy; temp.time = timee; q.push(temp); vis[xx][yy][timee] = 1; } } }