QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#723056#5605. A-Mazing PuzzleTheZoneAC ✓4564ms427172kbC++206.1kb2024-11-07 21:03:522024-11-07 21:03:53

Judging History

你现在查看的是最新测评结果

  • [2024-11-07 21:03:53]
  • 评测
  • 测评结果:AC
  • 用时:4564ms
  • 内存:427172kb
  • [2024-11-07 21:03:52]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;

int C, R, E;
unordered_set<int> walls;
unordered_map<int, int> dist;
unordered_map<int, int> bump;
vi unhasher(int h) {
    return {h % 51, (h = h / 51) % 51, (h = h / 51) % 51, (h = h / 51) % 51};
}

int hasher(int x1, int y1, int x2, int y2) {
    int h = 0;
    h += y2;
    h *= 51;
    h += x2;
    h *= 51;
    h += y1;
    h *= 51;
    h += x1;
    return h;
}

void update(int x1, int y1, int x2, int y2, int d, int b, queue<int> &q) {
    if(x1 == x2 && y1 == y2 && y1 != 0) return;
    int h = hasher(x1, y1, x2, y2);
    if(dist.find(h) == dist.end()) {
        dist[h] = d;
        bump[h] = b;
        q.push(h);
    }
    if(dist[h] < d) return;
    else if(dist[h] == d) {
        bump[h] = min(bump[h], b);
        return;
    }
    dist[h] = d;
    bump[h] = b;
}

bool isThereAWall(int x1, int y1, int x2, int y2) {
    if(x1 == x2 && y1 == y2) return false;
    if(x1 == x2 && x1 == E && max(y1, y2) == 1) return false;
    if(!x1 || !x2 || !y1 || !y2) return true;
    if(max(x1, x2) > C || max(y1, y2) > R) return true;
    if(x1 != x2) {
        if(x1 > x2) {
            swap(x1, x2);
        }
        return walls.find(x1 * 51 * 51 * 51 + y1 * 51 * 51) != walls.end();
    } else {
        if(y1 > y2) {
            swap(y1, y2);
        }
        return walls.find(x1 * 51 + y1) != walls.end();
    }
}



pair<int, int> nextStep(int x, int y, int dir) {
    if(y == 0) return {x, y};
    if(dir == 0) return {x, y+1};
    if(dir == 1) return {x+1, y};
    if(dir == 2) return {x, y-1};
    if(dir == 3) return {x-1, y};
    return {x, y};
}
int bumped = 0;

pair<int, int> nextS(int x, int y, int dir) {
    bumped = 0;
    auto p = nextStep(x, y, dir);
    if(!isThereAWall(x, y, p.first, p.second)) return {p.first, p.second};
    bumped = 1;
    return {x, y};
}





void solve() {
    cin >> C >> R >> E;
    int C1, R1, C2, R2;
    char D1, D2;
    cin >> C1 >> R1 >> D1 >> C2 >> R2 >> D2;
    int N1; cin >> N1;
    unordered_map<char, int> orientation;
    orientation['N'] = 0;
    orientation['E'] = 1;
    orientation['S'] = 2;
    orientation['W'] = 3;
    int d1 = orientation[D1];
    int d2 = orientation[D2];
    int diff = (d2 - d1 + 4) % 4;
    for(int i = 0; i < N1; i++) {
        int c1, r1; cin >> c1 >> r1;
        walls.insert(c1 * 51 + r1);
    }
    int N2; cin >> N2;
    for(int i = 0; i < N2; i++) {
        int c1, r1; cin >> c1 >> r1;
        walls.insert(c1 * 51 * 51 * 51 + r1 * 51 * 51);
    }
    dist[hasher(C1, R1, C2, R2)] = 0;
    bump[hasher(C1, R1, C2, R2)] = 0;
    queue<int> q;
    q.push(hasher(C1, R1, C2, R2));
    while(!q.empty()) {
        int curr = q.front();
        vi coords = unhasher(curr);
        // cout << coords[0] << " " << coords[1] << " " << coords[2] <<" " << coords[3] << "\n";
        // cout << dist[curr] << " " << bump[curr] << "\n";
        q.pop();
        if(coords[1] == 0) {
            if(coords[3] == 0) break;
            for(int i = 0; i < 4; i++) {
                auto nextc = nextS(coords[2], coords[3], i);
                update(coords[0], coords[1], nextc.first, nextc.second, dist[curr] + 1, bump[curr], q);
            }
        } if(coords[3] == 0) {
            for(int i = 0; i < 4; i++) {
                auto nextc = nextS(coords[0], coords[1], i);
                update(nextc.first, nextc.second, coords[2], coords[3],  dist[curr] + 1, bump[curr], q);
            }
        }
        for(int i = 0; i < 4; i++) {
            int bumper = 0;
            auto nextc1 = nextS(coords[0], coords[1], i);
            bumper += bumped;
            auto nextc2 = nextS(coords[2], coords[3], (i + diff) % 4);
            bumper += bumped;
            update(nextc1.first, nextc1.second, nextc2.first, nextc2.second, dist[curr] + 1, bump[curr] + bumper, q);
        }
    }
    cout << dist[hasher(E, 0, E, 0)] << " " << bump[hasher(E, 0, E, 0)] <<"\n";
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int T = 1;
    // cin >> T;
    while(T--) {
        solve();
    }
    return 0;
}


























































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































































Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3592kb

input:

7 4 4
3 2 S 6 3 S
6 1 1 1 2 1 3 2 3 5 1 5 3
11 2 1 3 1 3 2 5 2 6 2 2 3 4 3 5 3 6 3 3 4 6 4

output:

8 1

result:

ok single line: '8 1'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3668kb

input:

3 4 2
1 3 S 3 2 S
1 3 3
5 1 1 2 1 1 2 1 3 2 3

output:

7 2

result:

ok single line: '7 2'

Test #3:

score: 0
Accepted
time: 4564ms
memory: 427172kb

input:

50 50 4
15 28 W 9 43 E
49 11 47 42 33 3 4 36 49 21 21 15 34 43 5 32 35 3 21 7 1 40 4 22 44 11 40 46 43 13 26 32 6 44 25 31 46 26 7 45 4 18 10 10 21 3 20 31 8 34 40 42 1 48 43 18 17 9 39 17 2 48 25 39 35 45 43 8 2 22 17 6 46 33 1 38 6 28 25 29 32 45 12 11 20 8 48 14 9 2 24 45 38 1 20 34 5 46 24
50 13...

output:

91 52

result:

ok single line: '91 52'

Test #4:

score: 0
Accepted
time: 1393ms
memory: 179104kb

input:

50 50 25
1 50 N 50 50 E
1 45 25
1 16 37

output:

100 26

result:

ok single line: '100 26'

Test #5:

score: 0
Accepted
time: 0ms
memory: 3592kb

input:

10 10 1
10 1 N 10 2 N
0
81 9 1 9 2 9 3 9 4 9 5 9 6 9 7 9 8 9 9 8 10 8 9 8 8 8 7 8 6 8 5 8 4 8 3 8 2 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 6 10 6 9 6 8 6 7 6 6 6 5 6 4 6 3 6 2 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 4 10 4 9 4 8 4 7 4 6 4 5 4 4 4 3 4 2 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 2 10 2 9 2 8 2 7 2...

output:

120 4

result:

ok single line: '120 4'

Test #6:

score: 0
Accepted
time: 0ms
memory: 3560kb

input:

3 3 1
3 1 N 3 2 N
0
4 1 2 1 3 2 1 2 2

output:

13 4

result:

ok single line: '13 4'

Test #7:

score: 0
Accepted
time: 0ms
memory: 3628kb

input:

4 3 1
4 1 N 4 2 N
0
6 1 2 1 3 2 1 2 2 3 2 3 3

output:

15 4

result:

ok single line: '15 4'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3688kb

input:

5 5 1
2 4 N 2 1 S
2 2 2 2 4
3 1 1 1 3 3 3

output:

9 4

result:

ok single line: '9 4'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3532kb

input:

5 6 5
4 1 E 5 2 S
3 4 1 3 1 2 1
3 4 2 4 3 4 4

output:

11 2

result:

ok single line: '11 2'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3576kb

input:

4 4 3
1 2 E 4 1 W
2 3 2 4 1
5 1 1 2 1 1 3 3 2 3 3

output:

5 2

result:

ok single line: '5 2'

Test #11:

score: 0
Accepted
time: 1ms
memory: 3624kb

input:

10 10 2
1 1 E 6 1 W
1 6 1
1 1 1

output:

8 4

result:

ok single line: '8 4'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3588kb

input:

10 10 2
1 1 E 3 1 W
3 5 5 5 6 5 7
3 9 8 9 7 9 6

output:

6 1

result:

ok single line: '6 1'

Test #13:

score: 0
Accepted
time: 0ms
memory: 3660kb

input:

4 8 2
2 4 S 2 6 S
1 2 2
1 2 5

output:

8 1

result:

ok single line: '8 1'

Test #14:

score: 0
Accepted
time: 1ms
memory: 3692kb

input:

5 10 1
3 2 E 5 2 E
2 3 2 5 2
2 1 1 1 2

output:

9 3

result:

ok single line: '9 3'

Test #15:

score: 0
Accepted
time: 1ms
memory: 3800kb

input:

10 10 2
2 3 S 3 3 E
4 2 1 3 1 2 2 3 2
3 1 2 2 2 3 2

output:

11 2

result:

ok single line: '11 2'

Test #16:

score: 0
Accepted
time: 0ms
memory: 3860kb

input:

1 5 1
1 2 S 1 3 S
1 1 4
0

output:

3 0

result:

ok single line: '3 0'

Test #17:

score: 0
Accepted
time: 4281ms
memory: 425364kb

input:

50 50 49
14 39 N 30 28 N
50 1 3 30 21 26 11 32 37 7 14 46 49 44 46 17 16 46 38 42 25 7 9 38 29 22 15 6 20 20 34 49 7 48 27 19 18 27 8 29 17 22 41 11 8 6 43 20 29 13 47 14 46 31 43 18 43 40 28 39 35 2 13 31 47 23 35 37 46 3 1 18 11 9 39 31 22 28 12 15 14 24 23 35 47 16 3 13 19 35 5 6 30 18 46 44 2 30...

output:

74 0

result:

ok single line: '74 0'

Test #18:

score: 0
Accepted
time: 3283ms
memory: 333292kb

input:

50 50 28
39 24 W 50 30 N
48 4 35 19 38 23 43 12 49 26 35 20 40 24 9 29 41 2 16 23 36 26 40 45 5 31 10 41 49 34 44 39 4 2 8 40 11 10 40 10 13 18 6 18 28 2 4 17 22 41 38 20 29 6 35 35 20 42 47 32 21 20 38 17 33 42 45 21 4 39 32 49 32 26 3 11 28 12 6 28 47 2 42 29 14 22 23 34 40 47 23 47 26 39 16 1 17
...

output:

67 29

result:

ok single line: '67 29'

Test #19:

score: 0
Accepted
time: 1719ms
memory: 178304kb

input:

50 50 31
17 31 S 9 3 S
48 43 19 48 37 39 21 27 23 9 22 35 3 35 15 15 20 18 2 48 3 8 25 28 44 33 23 36 21 49 27 22 12 34 14 30 32 25 17 45 38 41 36 3 17 47 18 34 17 4 38 20 28 21 41 17 6 11 10 1 11 8 41 43 32 30 9 11 2 2 29 3 46 39 20 34 5 29 22 38 3 11 32 8 29 2 33 10 19 37 3 47 37 1 9 29 27
48 18 4...

output:

53 8

result:

ok single line: '53 8'

Test #20:

score: 0
Accepted
time: 3431ms
memory: 331076kb

input:

50 50 35
47 40 N 20 27 N
50 38 4 24 32 7 49 46 46 35 15 5 10 2 21 6 48 38 31 25 24 34 16 16 34 41 6 40 37 8 9 11 28 29 18 13 12 5 18 32 40 17 11 38 28 31 8 13 31 41 10 42 23 27 4 28 20 40 49 8 25 33 13 11 49 15 30 14 27 15 22 31 10 10 6 30 3 42 7 46 16 14 1 37 17 8 17 24 2 41 11 35 14 46 45 26 21 12...

output:

68 18

result:

ok single line: '68 18'

Test #21:

score: 0
Accepted
time: 0ms
memory: 3580kb

input:

10 10 1
3 1 N 3 2 N
0
81 9 1 9 2 9 3 9 4 9 5 9 6 9 7 9 8 9 9 8 10 8 9 8 8 8 7 8 6 8 5 8 4 8 3 8 2 7 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 6 10 6 9 6 8 6 7 6 6 6 5 6 4 6 3 6 2 5 1 5 2 5 3 5 4 5 5 5 6 5 7 5 8 5 9 4 10 4 9 4 8 4 7 4 6 4 5 4 4 4 3 4 2 3 1 3 2 3 3 3 4 3 5 3 6 3 7 3 8 3 9 2 10 2 9 2 8 2 7 2 6...

output:

42 4

result:

ok single line: '42 4'

Test #22:

score: 0
Accepted
time: 0ms
memory: 3636kb

input:

4 4 1
4 1 N 4 2 N
0
9 1 1 1 2 1 3 2 2 2 3 2 4 3 1 3 2 3 3

output:

24 4

result:

ok single line: '24 4'

Test #23:

score: 0
Accepted
time: 0ms
memory: 3888kb

input:

50 50 1
1 50 N 50 50 E
0
0

output:

100 1

result:

ok single line: '100 1'

Test #24:

score: 0
Accepted
time: 732ms
memory: 111056kb

input:

50 50 28
39 24 W 50 30 N
0
1 40 17

output:

67 28

result:

ok single line: '67 28'

Test #25:

score: 0
Accepted
time: 37ms
memory: 12080kb

input:

25 25 14
19 12 W 25 15 N
0
1 20 8

output:

34 13

result:

ok single line: '34 13'

Test #26:

score: 0
Accepted
time: 14ms
memory: 6292kb

input:

25 16 14
19 9 W 25 12 N
0
1 20 5

output:

31 13

result:

ok single line: '31 13'

Test #27:

score: 0
Accepted
time: 9ms
memory: 5284kb

input:

12 16 1
6 9 W 12 12 N
0
1 7 5

output:

31 13

result:

ok single line: '31 13'