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;
}