QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#232630#510. Car Vetartur0312AC ✓14ms7184kbC++142.2kb2023-10-30 18:01:092023-10-30 18:01:10

Judging History

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

  • [2023-10-30 18:01:10]
  • 评测
  • 测评结果:AC
  • 用时:14ms
  • 内存:7184kb
  • [2023-10-30 18:01:09]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define INF 2000000000

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;

int main() {
  int m, n;
  cin >> m >> n;
  vvi grid(m, vi(n));
  int start;
  int target;
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      cin >> grid[i][j];
      if (grid[i][j] == -1)
        start = n * i + j;
    }
  }
  int x, y;
  cin >> x >> y;
  x--;
  y--;
  target = n * x + y;
  vector<vector<ii>> adj(m * n);
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      // up
      if (grid[i][j] != -2 && i >= 2 && grid[i - 1][j] == grid[i - 2][j] &&
          grid[i - 1][j] != -2) {
        adj[i * n + j].push_back({(i - 2) * n + j, 1});
      }
      // down
      if (grid[i][j] != -2 && i + 2 < m && grid[i + 1][j] == grid[i + 2][j] &&
          grid[i + 1][j] != -2) {
        adj[i * n + j].push_back({(i + 2) * n + j, 1});
      }
      // right
      if (grid[i][j] != -2 && j + 2 < n && grid[i][j + 1] == grid[i][j + 2] &&
          grid[i][j + 1] != -2) {
        adj[i * n + j].push_back({i * n + j + 2, 1});
      }
      if (grid[i][j] != -2 && j >= 2 && grid[i][j - 1] == grid[i][j - 2] &&
          grid[i][j - 1] != -2) {
        adj[i * n + j].push_back({i * n + j - 2, 1});
      }
    }
  }
  vector<int> d(m * n, INF);
  vector<int> parent(m * n, -1);
  d[start] = 0;
  deque<int> q;
  q.push_front(start);
  while (!q.empty()) {
    int v = q.front();
    q.pop_front();
    for (auto edge : adj[v]) {
      int u = edge.first;
      int w = edge.second;
      if (d[v] + w < d[u]) {
        d[u] = d[v] + w;
        parent[u] = v;
        if (w == 1)
          q.push_back(u);
        else
          q.push_front(u);
      }
    }
  }
  if (d[target] == INF) {
    cout << "impossible";
  } else {
    vector<int> path = {target};
    while (parent[*path.rbegin()] != start) {
      path.push_back(parent[*path.rbegin()]);
    }
    reverse(path.begin(), path.end());
    for (int node : path) {
      cout << grid[node / n][node % n] << " ";
    }
    cout << "\n";
  }
}

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 3440kb

input:

4 4
8 8 -1 9
4 10 10 9
4 3 3 -2
16 16 2 2
3 3

output:

8 4 3 

result:

ok single line: '8 4 3 '

Test #2:

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

input:

4 4
8 8 -2 9
4 10 10 9
4 3 3 -1
16 16 2 2
3 3

output:

impossible

result:

ok single line: 'impossible'

Test #3:

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

input:

1 3
-1 1 1
1 3

output:

1 

result:

ok single line: '1 '

Test #4:

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

input:

3 1
-1
1
1
3 1

output:

1 

result:

ok single line: '1 '

Test #5:

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

input:

1 3
-1 1 1
1 2

output:

impossible

result:

ok single line: 'impossible'

Test #6:

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

input:

3 1
-1
1
1
2 1

output:

impossible

result:

ok single line: 'impossible'

Test #7:

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

input:

2 2
-1 1
-2 1
1 2

output:

impossible

result:

ok single line: 'impossible'

Test #8:

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

input:

3 3
1 1 2
4 -1 2
4 3 3
1 1

output:

impossible

result:

ok single line: 'impossible'

Test #9:

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

input:

3 3
1 1 2
3 3 2
-1 4 4
1 1

output:

4 2 1 

result:

ok single line: '4 2 1 '

Test #10:

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

input:

3 3
8 8 2
1 7 2
1 7 -1
1 1

output:

2 8 

result:

ok single line: '2 8 '

Test #11:

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

input:

7 7
1 2 2 3 3 4 4
1 7 6 6 5 5 14
8 7 9 10 11 11 14
8 18 9 10 12 13 15
19 18 17 16 12 13 15
19 -1 17 16 22 23 23
20 20 21 21 22 24 24
2 2

output:

18 7 

result:

ok single line: '18 7 '

Test #12:

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

input:

1 15
-1 1 1 2 2 3 3 4 4 5 5 6 6 7 7
1 15

output:

1 2 3 4 5 6 7 

result:

ok single line: '1 2 3 4 5 6 7 '

Test #13:

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

input:

7 7
13 13 14 14 15 15 -1
12 22 22 23 23 24 24
12 21 3 3 4 4 5
11 21 2 16 16 17 5
11 20 2 1 1 17 6
10 20 19 19 18 18 6
10 9 9 8 8 7 7
5 5

output:

15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 

result:

ok single line: '15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 '

Test #14:

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

input:

10 12
30 30 31 31 32 32 33 33 34 34 35 35
36 12 13 13 14 14 15 15 37 26 26 25
36 12 38 38 39 39 -2 16 37 40 40 25
41 11 -2 18 18 17 17 16 42 42 43 24
41 11 44 19 45 45 46 46 47 47 43 24
48 10 44 19 20 20 21 21 22 22 23 23
48 10 49 49 50 50 51 51 52 52 53 53
54 9 9 8 8 7 57 -1 1 1 2 2
54 55 55 56 56 ...

output:

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 

result:

ok single line: '1 2 3 4 5 6 7 8 9 10 11 12 13 ... 17 18 19 20 21 22 23 24 25 26 '

Test #15:

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

input:

4 4
1 1 2 2
-1 3 4 5
6 3 4 5
6 7 7 -2
4 2

output:

impossible

result:

ok single line: 'impossible'

Test #16:

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

input:

4 4
1 1 2 2
-1 3 4 5
6 3 4 5
6 -2 7 7
4 4

output:

impossible

result:

ok single line: 'impossible'

Test #17:

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

input:

10 10
16 16 20 28 26 39 39 7 7 8
-2 18 20 28 26 31 -2 6 23 8
21 18 -2 33 33 31 32 6 23 9
21 -2 22 22 15 15 32 5 43 9
30 30 29 29 25 4 4 5 43 10
-2 38 38 35 25 3 37 37 -2 10
36 14 42 35 13 3 17 0 24 11
36 14 42 19 13 2 17 0 24 11
40 40 -2 19 44 2 1 1 -2 -1
27 27 34 34 44 41 41 12 12 -2
7 8

output:

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

result:

ok single line: '11 10 9 8 7 6 5 4 3 2 1 0 '

Test #18:

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

input:

15 15
-2 72 72 58 58 71 71 55 55 42 42 -2 56 60 -2
65 67 67 0 0 1 1 2 50 50 94 94 56 60 49
65 -2 70 70 -2 96 96 2 26 26 38 38 43 43 49
77 18 18 19 37 4 3 3 82 82 45 -2 39 39 103
77 17 64 19 37 4 68 68 59 -2 45 54 90 21 103
92 17 64 -1 -2 5 20 20 59 24 73 54 90 21 93
92 16 53 53 101 5 97 75 75 24 73 ...

output:

19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 

result:

ok single line: '19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 '

Test #19:

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

input:

25 25
255 255 161 205 158 158 -2 282 282 68 221 221 125 125 -2 100 100 -2 241 241 152 152 107 107 227
93 93 161 205 -2 203 203 264 264 68 218 268 164 164 129 267 267 123 277 277 126 258 80 80 227
-2 211 211 -2 95 95 236 236 281 281 218 268 165 165 129 194 194 123 244 244 126 258 122 261 261
105 105 ...

output:

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

result:

ok single line: '52 51 50 49 48 47 46 45 44 43 ...3 12 11 10 9 8 7 6 5 4 3 2 1 0 '

Test #20:

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

input:

100 100
3390 3823 774 774 2568 2568 2604 2604 1252 2097 2097 1553 3914 3914 1528 964 1425 1413 926 926 -2 4042 4042 1267 956 771 771 4273 4273 2266 2266 -2 361 3289 3692 2681 -2 1687 1687 2120 2120 3262 160 -2 112 112 3121 832 2006 4088 4088 3461 3461 2926 2926 3889 3889 -2 2389 2389 1593 1593 2403 ...

output:

8 7 6 5 4 3 2 1 0 

result:

ok single line: '8 7 6 5 4 3 2 1 0 '

Test #21:

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

input:

100 100
1267 1041 1041 -2 495 2029 2029 722 343 4274 4274 269 4296 2903 1010 -2 1419 796 796 2067 2067 -2 1468 1468 2144 2144 450 450 843 843 4040 3660 82 82 4351 4351 773 773 3501 3686 2054 392 2913 2913 710 710 2657 -2 1738 -2 143 143 2748 2748 395 395 3783 3783 3555 2482 4020 4020 913 2654 1249 1...

output:

45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 

result:

ok single line: '45 44 43 42 41 40 39 38 37 36 ...3 12 11 10 9 8 7 6 5 4 3 2 1 0 '

Test #22:

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

input:

50 50
-2 148 148 -2 411 411 1097 1097 312 312 463 -2 347 347 905 796 796 237 237 628 628 -2 645 645 1083 1083 911 458 735 735 384 384 -2 318 318 1116 759 122 122 954 935 880 -2 514 514 243 243 340 1024 1024
494 121 -2 586 586 -2 612 609 1126 1126 463 721 721 -2 905 334 76 76 -2 450 429 776 776 870 2...

output:

impossible

result:

ok single line: 'impossible'

Test #23:

score: 0
Accepted
time: 2ms
memory: 3664kb

input:

99 99
2607 2434 2434 93 4364 4364 4151 2166 2166 -2 568 568 3701 46 46 1396 1396 -2 4175 647 647 2150 3754 3754 783 3172 3172 295 4059 191 191 -2 141 141 3479 -2 3601 3734 3990 3990 110 110 -2 620 3883 1224 1224 -2 3242 3242 4291 2460 2460 -2 4102 4102 2234 2234 4384 4384 2647 2647 4206 4206 1057 67...

output:

impossible

result:

ok single line: 'impossible'

Test #24:

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

input:

200 200
1807 11448 11448 4156 4156 4272 4272 8482 8482 8562 8562 -2 4230 17356 17356 15011 14228 14228 1383 1383 1111 1111 3278 3278 16322 466 10864 12200 12200 4674 18297 18297 8569 8569 -2 5929 5929 6413 6413 -2 16726 1917 1917 878 10369 13941 -2 1157 1157 -2 4113 4113 13965 8660 8660 16072 16072 ...

output:

45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 

result:

ok single line: '45 44 43 42 41 40 39 38 37 36 ...3 12 11 10 9 8 7 6 5 4 3 2 1 0 '

Test #25:

score: 0
Accepted
time: 6ms
memory: 6460kb

input:

250 250
18379 18379 4786 4786 -2 16757 16757 12147 12147 -2 12120 12120 8401 8401 28373 11306 11306 25759 25759 26289 26289 9192 20846 20846 5250 1235 1235 12962 12962 28265 28265 7154 25441 25441 115 18611 18611 9879 19613 19613 17043 7488 7488 17957 17957 -2 27516 27516 11366 11366 18345 18345 179...

output:

39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 

result:

ok single line: '39 38 37 36 35 34 33 32 31 30 ...3 12 11 10 9 8 7 6 5 4 3 2 1 0 '

Test #26:

score: 0
Accepted
time: 10ms
memory: 6456kb

input:

250 250
19203 -2 14098 14098 -2 746 746 8787 22683 22683 27089 27089 6934 6934 20362 9013 19334 19334 21537 4928 9542 11917 11917 22882 12416 23501 23501 -2 18414 18414 18746 18746 -2 8540 8540 -2 25175 7163 7163 19620 8406 8406 10240 10240 6765 -2 1178 20004 22173 8757 8757 8108 8108 20218 21765 21...

output:

67 66 65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0 

result:

ok single line: '67 66 65 64 63 62 61 60 59 58 ...3 12 11 10 9 8 7 6 5 4 3 2 1 0 '

Test #27:

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

input:

100 1
10
10
31
31
24
24
93
93
84
84
36
36
91
91
42
42
52
52
68
68
30
30
32
32
55
55
33
33
90
90
70
70
2
2
56
56
65
65
18
18
19
19
11
11
99
99
28
28
47
47
13
13
48
48
43
43
8
8
62
62
9
9
54
54
67
67
83
83
26
26
53
53
27
27
87
87
64
64
66
66
86
86
74
74
69
69
61
61
38
38
63
63
12
12
81
81
89
89
-1
-2
...

output:

89 81 12 63 38 61 69 74 86 66 64 87 27 53 26 83 67 54 9 62 8 43 48 13 47 28 99 11 19 18 65 56 2 70 90 33 55 32 30 68 52 42 91 36 84 93 24 31 10 

result:

ok single line: '89 81 12 63 38 61 69 74 86 66 ... 68 52 42 91 36 84 93 24 31 10 '

Test #28:

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

input:

1 100
61 61 25 25 42 42 0 0 75 75 99 99 79 79 44 44 37 37 64 64 92 92 57 57 71 71 10 10 56 56 87 87 14 14 55 55 9 9 98 98 21 21 95 95 66 66 41 41 23 23 34 34 11 11 47 47 90 90 35 35 67 67 49 49 4 4 31 31 29 29 8 8 15 15 68 68 78 78 3 3 94 94 96 96 53 53 13 13 7 7 26 26 86 86 22 22 93 93 -1 -2
1 1

output:

93 22 86 26 7 13 53 96 94 3 78 68 15 8 29 31 4 49 67 35 90 47 11 34 23 41 66 95 21 98 9 55 14 87 56 10 71 57 92 64 37 44 79 99 75 0 42 25 61 

result:

ok single line: '93 22 86 26 7 13 53 96 94 3 78...2 64 37 44 79 99 75 0 42 25 61 '

Test #29:

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

input:

2 30
45 45 24 24 59 59 52 52 58 58 55 55 16 16 17 17 26 26 14 14 28 28 40 40 1 1 31 31 -1 0
10 10 -2 42 42 -2 43 43 50 50 23 23 39 39 35 35 2 2 57 57 -2 6 6 51 51 33 33 18 18 0
1 1

output:

31 1 40 28 14 26 17 16 55 58 52 59 24 45 

result:

ok single line: '31 1 40 28 14 26 17 16 55 58 52 59 24 45 '

Test #30:

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

input:

40 2
64 23
64 23
17 20
17 20
51 -2
51 38
32 38
32 -2
31 77
31 77
3 -2
3 39
54 39
54 52
79 52
79 76
58 76
58 41
8 41
8 65
22 65
22 19
61 19
61 67
4 67
4 -2
30 0
30 0
60 56
60 56
6 68
6 68
2 -2
2 7
28 7
28 47
21 47
21 -2
-1 37
-2 37
1 1

output:

21 28 2 6 60 30 4 61 22 8 58 79 54 3 31 32 51 17 64 

result:

ok single line: '21 28 2 6 60 30 4 61 22 8 58 79 54 3 31 32 51 17 64 '

Test #31:

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

input:

5 11
51 51 18 18 39 39 44 44 4 4 16
1 29 29 14 14 -1 6 6 99 99 16
1 54 54 12 12 35 35 7 7 48 36
45 -2 11 11 -2 27 27 33 33 48 36
45 8 8 47 47 40 40 0 0 17 17
1 1

output:

impossible

result:

ok single line: 'impossible'

Test #32:

score: 0
Accepted
time: 3ms
memory: 3820kb

input:

100 100
2450 2450 2451 2451 2452 2452 2453 2453 2454 2454 2455 2455 2456 2456 2457 2457 2458 2458 2459 2459 2460 2460 2461 2461 2462 2462 2463 2463 2464 2464 2465 2465 2466 2466 2467 2467 2468 2468 2469 2469 2470 2470 2471 2471 2472 2472 2473 2473 2474 2474 2475 2475 2476 2476 2477 2477 2478 2478 24...

output:

2498 2497 2496 2495 2494 2493 2492 2491 2490 2489 2488 2487 2486 2485 2484 2483 2482 2481 2480 2479 2478 2477 2476 2475 2474 2473 2472 2471 2470 2469 2468 2467 2466 2465 2464 2463 2462 2461 2460 2459 2458 2457 2456 2455 2454 2453 2452 2451 2450 2449 2448 2447 2446 2445 2444 2443 2442 2441 2440 2439 ...

result:

ok single line: '2498 2497 2496 2495 2494 2493 ...3 12 11 10 9 8 7 6 5 4 3 2 1 0 '

Test #33:

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

input:

10 5
18 18 17 17 9
22 11 20 -2 9
22 11 20 16 16
2 2 3 3 4
1 -2 19 19 4
1 0 0 15 5
-2 8 8 15 5
-1 7 7 6 6
12 12 10 13 14
21 21 10 13 14
6 3

output:

7 6 5 4 3 2 1 0 

result:

ok single line: '7 6 5 4 3 2 1 0 '

Test #34:

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

input:

250 250
-2 17081 17081 16612 16612 -2 22223 22223 -2 16617 16617 19136 19136 19242 19242 22498 22498 17087 17087 -2 25513 25513 -2 25745 25745 -2 25690 25690 -2 24249 24249 21536 21536 25436 25436 -2 17727 17727 18382 18382 27214 27214 27520 27520 21350 21350 27986 27986 22866 22866 20785 20785 -2 2...

output:

15623 15622 15621 15620 15619 15618 15617 15616 15615 15614 15613 15612 15611 15610 15609 15608 15607 15606 15605 15604 15603 15602 15601 15600 15599 15598 15597 15596 15595 15594 15593 15592 15591 15590 15589 15588 15587 15586 15585 15584 15583 15582 15581 15580 15579 15578 15577 15576 15575 15574 ...

result:

ok single line: '15623 15622 15621 15620 15619 ...3 12 11 10 9 8 7 6 5 4 3 2 1 0 '

Test #35:

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

input:

50 50
1028 709 709 875 875 938 938 -2 1010 1010 780 780 896 896 888 888 809 809 1070 1070 628 628 -2 1109 1109 1160 1160 1101 1101 1116 1116 882 882 681 681 742 742 971 971 1046 1046 743 743 1098 1098 1137 1137 -2 963 963
1028 552 552 553 553 554 554 555 555 556 556 557 557 558 558 559 559 560 560 5...

output:

623 622 621 620 619 618 617 616 615 614 613 612 611 610 609 608 607 606 605 604 603 602 601 600 599 598 597 596 595 594 593 592 591 590 589 588 587 586 585 584 583 582 581 580 579 578 577 576 575 574 573 572 571 570 569 568 567 566 565 564 563 562 561 560 559 558 557 556 555 554 553 552 551 550 549 ...

result:

ok single line: '623 622 621 620 619 618 617 61...3 12 11 10 9 8 7 6 5 4 3 2 1 0 '

Test #36:

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

input:

250 250
55741 55741 6673 6673 44875 44875 62146 62146 5027 5027 38021 38021 19633 19633 9567 9567 57407 57407 131 131 34287 34287 16953 16953 42881 42881 21316 21316 24748 24748 31415 31415 43989 43989 32268 32268 53544 53544 31880 31880 30350 30350 25344 25344 23296 23296 52134 52134 35864 35864 37...

output:

55031 35922 17003 47203 60141 6159 17605 9345 36390 59805 11951 1521 42085 3348 42523 37386 10514 18510 62090 61891 60829 47788 57559 34658 48323 7862 50519 55732 26768 19814 2812 17859 10080 99 39106 36882 10877 47971 2885 47512 31076 59181 29311 55869 58384 48814 20037 48713 18201 24391 46246 6020...

result:

ok single line: '55031 35922 17003 47203 60141 ...21 5027 62146 44875 6673 55741 '

Test #37:

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

input:

50 50
985 985 2093 2093 1072 1072 822 822 1578 1578 443 443 1214 1214 1344 1344 688 688 1645 1645 26 26 2388 2388 365 365 940 940 2016 2016 394 394 2253 2253 1114 1114 1186 1186 477 477 2374 2374 685 685 1952 1952 1247 1247 2150 2329
1629 1629 2099 2099 -2 75 75 867 867 397 397 32 32 1925 1925 2382 ...

output:

829 240 888 163 455 889 1573 1439 707 1060 30 2106 2157 1943 2117 1688 752 72 1175 144 918 2423 2266 1691 876 2073 528 720 2346 1430 1020 566 1157 1901 298 773 988 833 770 1572 1932 1400 2240 2172 1230 141 1820 119 34 2270 1821 2192 1543 1198 1277 1231 2378 2236 137 2169 292 2453 2393 1670 313 1289 ...

result:

ok single line: '829 240 888 163 455 889 1573 1...214 443 1578 822 1072 2093 985 '