Problem D - Getaway
The Problem
Selma and Louis are two of the most dangerous bank robbers in Man-hat'em City. The main reason they are so good, and never got caught, is their ability to create perfect escape plans. The problem is they are getting old and their mind isn't what it used to be, so they are looking for someone to create a program that automatically creates these escape routes for them.
A well known figure in the crime scene of Man-hat'em told them you were the best guy for the job.
Man-hat'em is a very well organized city. Its streets are layed out in a grid and the distance between each crossroad is always the same. However some streets are one way only and some don't even allow cars.
Besides having to make a quick getaway Selma and Louis have one other problem. The city has recently installed a surveillance system. Cameras have been installed in some crossroads but only one camera is monitored at each given time. The success of their getaway is drastically reduced if they are spotted during their escape so their escape route must avoid any crossing that is being monitored. Luckily, their friend Tony managed to get the surveillance system scheduling plans.
Your job will be to create a program that, given a certain partial map of the city and the surveillance system scheduling, will compute the optimum escape route. The following can be assumed to be always true:
- The robbery will always take place at the northwest of the map;
- The hideaway will always be at the southeast of the map;
- There is always a possible escape route;
- The time needed to get from one crossroad to the next is always the same, and, for simplicity sake, can be considered as being one time unit.
- The escape route must never pass a crossing that is being monitorized at that time;
- To avoid getting caught on camera Selma and Louis can wait any units of time at a given crossroad.
Input
The input file contains several test cases, each of them as describes below. - The input starts by stating the number of vertical roads (nv) and horizontal roads (nh) in a single line. With 1 <= nv,nh <= 100.
- The following line will contain the number (r) of traffic restrictions in the city. With 0 <= r <= 500.
- Each of the following r lines will contain a restriction of the form: x1 y1 x2 y2. Meaning that traffic isn't allowed from the crossroad with coordinates (x1, y1) to the crossroad with coordinates (x2, y2).
- The next line will contain the number (m) of scheduled crossroad monitorizations. With 0 <= m <= 500.
- Each of the following m lines will contain the monitorization information in the form: t x y. Where t is the time counting from the start of the getaway and (x, y) are the coordinates of the crossroad being monitored. All these m lines will have different values for t. With 0 <= t <= 500.
Output
For each test case, the output will contain a single line stating the minimum number of time units needed for a perfect getaway. Example Input
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
Example Output
6
Explanation of the example output The plan starts at (0,0) at time 0. They then proceed to (0,1) where they intended to turn left heading to (1,1). Thanks to Tony, they know someone will be monitoring them at (1,1) by the time they get there, so they wait for one time unit. They arrive at (1,1) at time 3, where they wait another time unit as they know they will be monitored at (2,1) at time 4. After this second wait, they proceed to (2,1) and then to (2,2) where they arrive at time 6.
2005 Programming Contest of Porto University
Round 2, 28 of September of 2005
(Author: Andr Restivo - FEUP)
目描述：
一格的道路，而且道路只存在四方向，然而有一些器在 t 行，也就是在第
t 秒不能通。求左上掉右下的最短距。
目解法：
在 BFS 的候，判定那法走，多停留一秒，也有可能生多停秒可能。
以器是期性的，一秒哪看啊！
#include <stdio.h>
#include <string.h>
#include <queue>
#include <set>
using namespace std;
int dd[105][105][4];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int main() {
int n, m, q;
int i, j, k;
int sx, sy, ex, ey, tx, ty, tt;
int x, y, time;
while(scanf("%d %d", &n, &m) == 2) {
for(i = 0; i < n; i++)
for(j = 0; j < m; j++)
for(k = 0; k < 4; k++)
dd[i][j][k] = 1;
set<int> monitor[105][105];
scanf("%d", &q);
while(q--) {
scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
for(j = 0; j < 4; j++) {
tx = sx+dx[j], ty = sy+dy[j];
if(tx == ex && ty == ey)
dd[sx][sy][j] = 0;//can'c allow
}
}
scanf("%d", &q);
while(q--) {
scanf("%d %d %d", &time, &sx, &sy);
monitor[sx][sy].insert(time);
}
queue<int> X, Y, T;
X.push(0), Y.push(0), T.push(0);
int dist[105][105] = {};
memset(dist, 63, sizeof(dist));
dist[0][0] = 0;
if(n == 1 && m == 1) {
puts("0");
continue;
}
while(!X.empty()) {
x = X.front(), X.pop();
y = Y.front(), Y.pop();
time = T.front(), T.pop();
time++;
for(i = 0; i < 4; i++) {
if(dd[x][y][i] == 0) continue;
tx = x+dx[i], ty = y+dy[i];
if(tx < 0 || ty < 0 || tx >= n || ty >= m)
continue;
tt = time;
while(monitor[tx][ty].find(tt) != monitor[tx][ty].end())
tt++;
if(tt < dist[tx][ty]) {
dist[tx][ty] = tt;
X.push(tx), Y.push(ty), T.push(tt);
}
}
}
printf("%d\n", dist[n-1][m-1]);
}
return 0;
}
文章定位：
