QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#98970	#5605. A-Mazing Puzzle	Nicolas125841	AC ✓	6970ms	370824kb	C++14	6.8kb	2023-04-21 03:53:02	2023-04-21 03:53:06

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-04-21 03:53:06]
评测

测评结果：AC
用时：6970ms
内存：370824kb

查看

[2023-04-21 03:53:02]
提交

answer

#include <bits/stdc++.h>

using namespace std;

struct Robot{
    int c, r;
    char d;
};

struct Dist{
    int c, r, d;

    Dist(int R, int C, int D): c(C), r(R), d(D) {}
};

class DCompare{
    public:
    bool operator()(const Dist &a, const Dist &b){
        return b.d < a.d;
    }
};

char dirs[4] = {'N', 'E', 'S', 'W'};
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};

vector<vector<int>> dist(51, vector<int>(50, 1000000));

class VCompare{
    public:
    bool operator()(const vector<int> &a, const vector<int> &b){
        if(a[5] + dist[a[2]][a[3]] == b[5] + dist[b[2]][b[3]])
            return a[4] > b[4];				
            
        return a[5] + dist[a[2]][a[3]] > b[5] + dist[b[2]][b[3]];
    }
};

int main(){
    cin.tie(NULL)->sync_with_stdio(false);
    
    int c, r, e;
    cin >> c >> r >> e;
    
    e--;

    int rr, rc;
    char rd;

    cin >> rc >> rr >> rd;

    Robot r1{ .c = rc-1, .r = r-rr, .d = rd };

    cin >> rc >> rr >> rd;

    Robot r2{ .c = rc-1, .r = r-rr, .d = rd };
    
    int angle = 0, r1d = 0, r2d = 0;
    
    for(int i = 0; i < 4; i++) {
        if(dirs[i] == r1.d)
            r1d = i;
        if(dirs[i] == r2.d)
            r2d = i;
    }
    
    if(r1d <= r2d)
        angle = r2d-r1d;
    else
        angle = 4+r2d-r1d;
                    
    vector<vector<int>> block(r+1, vector<int>(c, 0));
        
    int n, blockc, blockr;
    cin >> n;
    
    for(int i = 0; i < n; i++) {
        cin >> blockc >> blockr;
        blockc--;
        blockr = r-blockr;

        block[blockr][blockc] |= 1;
        block[blockr-1][blockc] |= 4;						
    }
    
    cin >> n;
    
    for(int i = 0; i < n; i++) {
        cin >> blockc >> blockr;
        blockc--;
        blockr = r-blockr;

        block[blockr][blockc] |= 2;
        block[blockr][blockc+1] |= 8;						
    }
    
    for(int i = 0; i <= r; i++) {
        block[i][0] |= 8;
        block[i][c-1] |= 2;
    }
    
    for(int i = 0; i < c; i++) {
        block[0][i] |= 1;
        block[r][i] |= 4;
        if(i != e) {
            block[r-1][i] |= 4;
            block[r][i] |= 1;
        }
    }

    priority_queue<Dist, vector<Dist>, DCompare> pq;
           
    pq.emplace(r, e, 0);
    
    dist[r][e] = 0;
    
    while(!pq.empty()) {
        Dist cur = pq.top();

        pq.pop();

        if(dist[cur.r][cur.c] == cur.d) {
            for(int i = 0; i < 4; i++) {
                if(((block[cur.r][cur.c]>>i)&1) == 1 || dist[cur.r+dr[i]][cur.c+dc[i]] <= cur.d+1)
                    continue;
                
                dist[cur.r+dr[i]][cur.c+dc[i]] = cur.d+1;
                pq.emplace(cur.r+dr[i], cur.c+dc[i], cur.d+1);
            }
        }
    }

    vector<vector<vector<int>>> cost((r+1)*c, vector<vector<int>>((r+1)*c, vector<int>(2, 1000000)));          

    priority_queue<vector<int>, vector<vector<int>>, VCompare> spq;
    
    spq.push({r1.r, r1.c, r2.r, r2.c, 0, 0});

    cost[r1.r*c+r1.c][r2.r*c+r2.c][0] = dist[r2.r][r2.c];
    cost[r1.r*c+r1.c][r2.r*c+r2.c][1] = 0;
    
    block[r][e] = 15;
    	
    int prev = dist[r2.r][r2.c];

    while(!spq.empty()) {
        vector<int> cur = spq.top();

        spq.pop();

        if(cost[cur[0]*c+cur[1]][cur[2]*c+cur[3]][0] < cur[5] + dist[cur[2]][cur[3]])
            continue;
        else if(cost[cur[0]*c+cur[1]][cur[2]*c+cur[3]][0] == cur[5] + dist[cur[2]][cur[3]])
            if(cost[cur[0]*c+cur[1]][cur[2]*c+cur[3]][1] < cur[4])
                continue;
                    
        for(int i = 0; i < 4; i++) {
            if(((block[cur[0]][cur[1]]>>i)&1) == 1) {
                if(((block[cur[2]][cur[3]]>>((i+angle)%4))&1)==1 || (cur[2] == r && cur[3] == e))
                    continue;
                
                int nr1 = cur[0], nc1 = cur[1];
                int nr2 = cur[2] + dr[(i+angle)%4], nc2 = cur[3] + dc[(i+angle)%4];
                int bump = (cur[0] == r && cur[1] == e) ? 0 : 1;
                
                if(nr1 == nr2 && nc1 == nc2 && !(cur[2] == r && cur[3] == e))
                    continue;
                                    
                if(cost[nr1*c+nc1][nr2*c+nc2][0] > cur[5] + 1 + dist[nr2][nc2]) {
                    cost[nr1*c+nc1][nr2*c+nc2][0] = cur[5] + 1 + dist[nr2][nc2];
                    cost[nr1*c+nc1][nr2*c+nc2][1] = cur[4] + bump;
                    
                    spq.push({nr1, nc1, nr2, nc2, cur[4] + bump, cur[5] + 1});
                }else if(cost[nr1*c+nc1][nr2*c+nc2][0] == cur[5] + 1 + dist[nr2][nc2] && cost[nr1*c+nc1][nr2*c+nc2][1] > cur[4] + bump) {
                    cost[nr1*c+nc1][nr2*c+nc2][0] = cur[5] + 1 + dist[nr2][nc2];
                    cost[nr1*c+nc1][nr2*c+nc2][1] = cur[4] + bump;
                    
                    spq.push({nr1, nc1, nr2, nc2, cur[4] + bump, cur[5] + 1});
                }					
            }else {				
                int nr1 = cur[0] + dr[i], nc1 = cur[1] + dc[i];
                int nr2 = cur[2] + dr[(i+angle)%4], nc2 = cur[3] + dc[(i+angle)%4];
                int bump = 0;
                                    
                if(((block[cur[2]][cur[3]]>>((i+angle)%4))&1)==1) {
                    if(!(cur[2] == r && cur[3] == e))
                        bump = 1;
                    
                    nr2 = cur[2];
                    nc2 = cur[3];
                }
                
                if(nr1 == nr2 && nc1 == nc2 && !(cur[2] == r && cur[3] == e))
                    continue;
                
                if(cost[nr1*c+nc1][nr2*c+nc2][0] > cur[5] + 1 + dist[nr2][nc2]) {
                    cost[nr1*c+nc1][nr2*c+nc2][0] = cur[5] + 1 + dist[nr2][nc2];
                    cost[nr1*c+nc1][nr2*c+nc2][1] = cur[4] + bump;
                    
                    spq.push({nr1, nc1, nr2, nc2, cur[4] + bump, cur[5] + 1});
                }else if(cost[nr1*c+nc1][nr2*c+nc2][0] == cur[5] + 1 + dist[nr2][nc2] && cost[nr1*c+nc1][nr2*c+nc2][1] > cur[4] + bump) {
                    cost[nr1*c+nc1][nr2*c+nc2][0] = cur[5] + 1 + dist[nr2][nc2];
                    cost[nr1*c+nc1][nr2*c+nc2][1] = cur[4] + bump;
                    
                    spq.push({nr1, nc1, nr2, nc2, cur[4] + bump, cur[5] + 1});
                }
            }
        }
    }
        
    int mina = 1000000, minb = 1000000;

    for(int i = 0; i <= r; i++) {
        for(int j = 0; j < c; j++) {
            if(cost[r*c+e][i*c+j][0] < mina) {
                mina = cost[r*c+e][i*c+j][0];
                minb = cost[r*c+e][i*c+j][1];
            }else if(cost[r*c+e][i*c+j][0] == mina && cost[r*c+e][i*c+j][1] < minb) {
                mina = cost[r*c+e][i*c+j][0];
                minb = cost[r*c+e][i*c+j][1];
            }
        }
    }
    
    cout << mina << " " << minb << "\n";
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 2ms

memory: 3504kb

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: 2ms

memory: 3524kb

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: 6654ms

memory: 364900kb

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: 4075ms

memory: 365792kb

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: 2ms

memory: 4084kb

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: 2ms

memory: 3424kb

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: 3432kb

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: 0ms

memory: 3532kb

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: 2ms

memory: 3488kb

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: 1ms

memory: 3448kb

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: 2ms

memory: 4120kb

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: 4216kb

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: 2ms

memory: 3508kb

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: 3ms

memory: 3624kb

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: 4ms

memory: 4148kb

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: 2ms

memory: 3412kb

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: 6389ms

memory: 364920kb

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: 6970ms

memory: 370584kb

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: 6791ms

memory: 365124kb

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: 6715ms

memory: 370824kb

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: 3ms

memory: 4128kb

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: 2ms

memory: 3512kb

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: 266ms

memory: 358888kb

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: 2333ms

memory: 362024kb

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: 86ms

memory: 26784kb

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: 34ms

memory: 13520kb

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: 7ms

memory: 5804kb

input:

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

output:

31 13

result:

ok single line: '31 13'