题目描述Selma\texttt{Selma}Selma和Louis\texttt{Louis}Louis是Man-hat’em\texttt{Man-hatem}Man-hat’em城中最危险的银行劫匪。该城市街道呈网格状相邻路口之间的距离相同。部分街道是单行道部分街道禁止通行。城市安装了监控系统某些路口在特定时间会被监控同一时刻仅有一个摄像头处于监控状态。劫匪的逃跑路线必须避开任何正在被监控的路口且可以在任意路口等待任意单位时间。抢劫地点始终位于地图西北角藏身地点始终位于东南角。已知从一交叉口到相邻交叉口需要111个时间单位。要求计算完成完美逃跑所需的最少时间单位数。输入格式输入包含多个测试用例。每个测试用例首先一行给出纵向道路数nvnvnv和横向道路数nhnhnh1≤nv,nh≤1001 \le nv, nh \le 1001≤nv,nh≤100。随后一行给出交通限制数量rrr0≤r≤5000 \le r \le 5000≤r≤500接着rrr行每行包含四个整数x1,y1,x2,y2x_1, y_1, x_2, y_2x1​,y1​,x2​,y2​表示禁止从(x1,y1)(x_1, y_1)(x1​,y1​)通行到(x2,y2)(x_2, y_2)(x2​,y2​)。接下来一行给出监控调度数量mmm0≤m≤5000 \le m \le 5000≤m≤500随后mmm行每行包含t,x,yt, x, yt,x,y表示在时间ttt时路口(x,y)(x, y)(x,y)被监控所有ttt值互不相同0≤t≤5000 \le t \le 5000≤t≤500。输出格式对于每个测试用例输出一行表示完成完美逃跑所需的最少时间单位数。样例输入3 3 6 0 0 1 0 1 0 0 0 1 0 2 0 0 1 0 2 1 2 0 2 1 2 2 2 2 2 1 1 4 2 1样例输出6题目分析本题要求在带有单向限制和动态监控的网格图中从西北角(0,0)(0,0)(0,0)到东南角(nv−1,nh−1)(nv-1, nh-1)(nv−1,nh−1)寻找最短时间路径。与普通最短路径问题不同本题中节点是否可访问取决于到达时间且允许在节点等待以避开监控。由于存在等待操作传统的BFS\texttt{BFS}BFS不能直接使用因为同一个节点可能在不同时间被多次访问且先到达不一定最优。需要采用优先队列实现的Dijkstra\texttt{Dijkstra}Dijkstra算法以时间作为距离度量。状态包含当前位置(x,y)(x, y)(x,y)和到达时间ttt。从当前状态出发尝试向四个方向移动若目标位置在网格内且没有交通限制则计算到达时间t1t1t1若该时间目标位置正在被监控则递增时间直到不再被监控。将新状态加入优先队列。需要注意的是同一节点可能在不同时间被多次访问且后到达的状态可能因避开监控而具有更优的后续路径。因此不能简单地用visited数组标记节点已访问而应记录到达每个节点的最早时间仅当新时间更早时才更新。然而由于存在等待操作到达时间较晚的状态仍可能产生更优解因此更稳妥的做法是允许重复访问依靠优先队列按时间顺序扩展首次到达终点的时间即为最短时间。解题思路使用三维数组或哈希表存储交通限制信息记录从(x1,y1)(x_1, y_1)(x1​,y1​)到(x2,y2)(x_2, y_2)(x2​,y2​)是否禁止通行。使用哈希表monitor存储监控调度键为时间ttt值为被监控路口的编码。采用优先队列实现Dijkstra\texttt{Dijkstra}Dijkstra算法。初始状态为(0,0,0)(0, 0, 0)(0,0,0)即起点、时间000。每次从队列中取出时间最小的状态若已到达终点则输出时间并结束。否则尝试向四个方向移动对于每个方向计算新坐标(xx,yy)(xx, yy)(xx,yy)检查是否在网格范围内且没有交通限制。计算到达时间ttt1tt t 1ttt1然后检查在时间tttttt时(xx,yy)(xx, yy)(xx,yy)是否被监控若被监控则递增tttttt直到不再被监控。将新状态(xx,yy,tt)(xx, yy, tt)(xx,yy,tt)加入优先队列。由于优先队列按时间升序扩展首次到达终点的状态对应的时间即为最短时间。时间复杂度为O(Vlog⁡V)O(V \log V)O(VlogV)其中VVV为状态数受监控时间上限500500500和网格规模限制实际状态数有限能够高效运行。代码实现// Getaway// UVa ID: 949// Verdict: Accepted// Submission Date: 2017-03-13// UVa Run Time: 0.000s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structstate{intx,y,seconds;booloperator(conststatea)const{returnsecondsa.seconds;}};intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intgrid[100][100][4][4],visited[100][100],nv,nh;unordered_mapint,intmonitor;intoffset[4][2]{{0,-1},{1,0},{0,1},{-1,0}};while(cinnvnh){memset(grid,0,sizeof(grid));memset(visited,0,sizeof(visited));monitor.clear();intr,x1,y1,x2,y2;cinr;for(inti1;ir;i){cinx1y1x2y2;grid[x1][y1][x2-x11][y2-y11]1;}intm,t;cinm;for(inti1;im;i){cintx1y1;monitor[t]y1*nvx1;}priority_queuestateunvisited;unvisited.push(state{0,0,0});visited[0][0]1;while(!unvisited.empty()){state currentunvisited.top();unvisited.pop();if(current.x(nv-1)current.y(nh-1)){coutcurrent.seconds\n;break;}intxcurrent.x,ycurrent.y;for(intk0;k4;k){intxxcurrent.xoffset[k][0],yycurrent.yoffset[k][1];if(xx0xxnvyy0yynh)if(!visited[xx][yy]!grid[x][y][offset[k][0]1][offset[k][1]1]){visited[xx][yy]1;intttcurrent.seconds1;while(monitor.find(tt)!monitor.end()monitor[tt](yy*nvxx))tt;unvisited.push(state{xx,yy,tt});}}}}return0;}总结本题的关键在于处理动态监控带来的时间依赖性。通过优先队列实现的Dijkstra\texttt{Dijkstra}Dijkstra算法按时间顺序扩展状态能够正确处理等待操作和监控规避。交通限制使用四维数组存储监控调度使用哈希表存储查询效率高。由于首次到达终点的状态时间最小直接输出即可。时间复杂度为O(Vlog⁡V)O(V \log V)O(VlogV)空间复杂度为O(V)O(V)O(V)能够高效处理题目规模的数据。