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;
}
文章定位: