解題區/解題區 - UVa

UVa 298 - Race Tracks

contents

  1. 1. Problem
  2. 2. Sample input
  3. 3. Sample output
  4. 4. Solution

Problem

給定一個 N * M 的地圖，接著將會從起點出發抵達終點，一開始的速度為 (0, 0)，在下一個時刻，每一個維度的速度可以調整 -3, -2, -1, 0, 1, 2, 3 (也就是加速度)，但是速度的絕對值必須小於等於 3，同時給定這張地圖的矩形障礙物，移動的過程中不用考慮會不會遇到障礙物，只需要考慮跳躍落下的地點是否有障礙物。

Sample input

1
2
3
4
5
6
7
8
9
10
2
5 5
4 0 4 4
1
1 4 2 3
3 3
0 0 2 2
2
1 1 0 2
0 2 1 1

Sample output

1
2
Optimal solution takes 7 hops.
No solution.

Solution

bfs 廣度搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <stdio.h> 
#include <queue>
#include <string.h>
#include <algorithm>
#include <stdlib.h>
using namespace std;
int g[64][64];
int testcase, N, M, P;
int sx, sy, ex, ey;
void bfs() {
    int dp[64][64][8][8] = {};
    queue<int> X, Y, VX, VY;
    int x, y, vx, vy, tx, ty, dx, dy;
    dp[sx][sy][0+3][0+3] = 1;
    X.push(sx), Y.push(sy), VX.push(0), VY.push(0);
    while(!X.empty()) {
        x = X.front(), X.pop();
        y = Y.front(), Y.pop();
        vx = VX.front(), VX.pop();
        vy = VY.front(), VY.pop();
        if(x == ex && y == ey) {
            printf("Optimal solution takes %d hops.\n", dp[x][y][vx+3][vy+3]-1);
            return;
        }
        for(int i = -1; i <= 1; i++) {
            for(int j = -1; j <= 1; j++) {
                dx = vx + i, dy = vy + j;
                if(abs(dx) <= 3 && abs(dy) <= 3) {
                    tx = x + dx, ty = y + dy;
                    if(tx < 0 || tx >= N || ty < 0 || ty >= M || dp[tx][ty][dx+3][dy+3])
                        continue;
                    if(g[tx][ty])
                        continue;
                    dp[tx][ty][dx+3][dy+3] = dp[x][y][vx+3][vy+3] + 1;
                    X.push(tx), Y.push(ty);
                    VX.push(dx), VY.push(dy);
                } 
            }
        }
    }
    puts("No solution.");
}
int main() {
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &N, &M);
        scanf("%d %d %d %d", &sx, &sy, &ex, &ey);
        scanf("%d", &P);
        memset(g, 0, sizeof(g));
        for(int i = 0; i < P; i++) {
            int lx, ly, rx, ry;
            scanf("%d %d %d %d", &lx, &rx, &ly, &ry);
            for(int p = lx; p <= rx; p++)
                for(int q = ly; q <= ry; q++)
                    g[p][q] = 1;
        }
        bfs();
    }
    return 0;
}