Task: | Sokkelo |
Sender: | intoo |
Submission time: | 2022-01-22 16:41:11 +0200 |
Language: | C++ (C++17) |
Status: | READY |
Result: | 100 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 28 |
#2 | ACCEPTED | 72 |
test | verdict | time | group | |
---|---|---|---|---|
#1 | ACCEPTED | 0.01 s | 1, 2 | details |
#2 | ACCEPTED | 0.01 s | 1, 2 | details |
#3 | ACCEPTED | 0.01 s | 1, 2 | details |
#4 | ACCEPTED | 0.08 s | 2 | details |
#5 | ACCEPTED | 0.15 s | 2 | details |
#6 | ACCEPTED | 0.15 s | 2 | details |
#7 | ACCEPTED | 0.01 s | 1, 2 | details |
#8 | ACCEPTED | 0.17 s | 2 | details |
#9 | ACCEPTED | 0.17 s | 2 | details |
#10 | ACCEPTED | 0.01 s | 1, 2 | details |
#11 | ACCEPTED | 0.25 s | 2 | details |
#12 | ACCEPTED | 0.01 s | 1, 2 | details |
#13 | ACCEPTED | 0.19 s | 2 | details |
#14 | ACCEPTED | 0.01 s | 1, 2 | details |
#15 | ACCEPTED | 0.18 s | 2 | details |
#16 | ACCEPTED | 0.01 s | 2 | details |
#17 | ACCEPTED | 0.01 s | 2 | details |
Compiler report
input/code.cpp: In function 'int main()': input/code.cpp:51:14: warning: 'bx' may be used uninitialized in this function [-Wmaybe-uninitialized] if (o[by][bx]) { ~~~~~~~~^ input/code.cpp:51:14: warning: 'by' may be used uninitialized in this function [-Wmaybe-uninitialized]
Code
#include <iostream> #include <vector> #include <queue> #include <tuple> using namespace std; using ll = long long; int n, m; pair<int, int> ds[4] = {{-1, 0}, {0, -1}, {0, 1}, {1, 0}}; bool t[1001][1001]; int o[1001][1001]; vector<pair<int, int>> s[3]; int d[1001][1001]; bool z[1001][1001]; void dfs(int y, int x, int v) { if (y < 0 || n <= y || x < 0 || m <= x) return; if (t[y][x]) return; if (o[y][x]) return; o[y][x] = v; s[v].emplace_back(y, x); for (auto [dy, dx] : ds) { dfs(y+dy, x+dx, v); } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m; int ay, ax, by, bx; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { char c; cin >> c; t[i][j] = c == '#'; if (c == 'A') { ay = i; ax = j; } if (c == 'B') { by = i; bx = j; } } } dfs(ay, ax, 1); if (o[by][bx]) { cout << 1 << endl; return 0; } dfs(by, bx, 2); int mi = 1e9; priority_queue<tuple<int, int, int>> q; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { d[i][j] = 1e9; } } d[ay][ax] = 0; q.emplace(0, ay, ax); while (!q.empty()) { auto [c, y, x] = q.top(); q.pop(); c = -c; if (z[y][x]) continue; z[y][x] = 1; for (auto [dy, dx] : ds) { int ny = y+dy, nx = x+dx; if (ny < 0 || n <= ny || nx < 0 || m <= nx) continue; if (d[y][x] + (o[ny][nx] != 1) < d[ny][nx]) { d[ny][nx] = d[y][x] + (o[ny][nx] != 1); if (o[ny][nx] == 2) { mi = min(mi, d[ny][nx]); } else { q.emplace(-d[ny][nx], ny, nx); } } } } cout << mi << endl; }
Test details
Test 1
Group: 1, 2
Verdict: ACCEPTED
input |
---|
20 20 #################### #A.................# #..................# #..................# ... |
correct output |
---|
1 |
user output |
---|
1 |
Test 2
Group: 1, 2
Verdict: ACCEPTED
input |
---|
20 20 #################### #A.................# #..................# #..................# ... |
correct output |
---|
2 |
user output |
---|
2 |
Test 3
Group: 1, 2
Verdict: ACCEPTED
input |
---|
20 20 #################### #A.................# #..................# #..................# ... |
correct output |
---|
9 |
user output |
---|
9 |
Test 4
Group: 2
Verdict: ACCEPTED
input |
---|
1000 1000 ##############################... |
correct output |
---|
1 |
user output |
---|
1 |
Test 5
Group: 2
Verdict: ACCEPTED
input |
---|
1000 1000 ##############################... |
correct output |
---|
2 |
user output |
---|
2 |
Test 6
Group: 2
Verdict: ACCEPTED
input |
---|
1000 1000 ##############################... |
correct output |
---|
335 |
user output |
---|
335 |
Test 7
Group: 1, 2
Verdict: ACCEPTED
input |
---|
20 20 #################### #####.############## ###.....############ ##.......########### ... |
correct output |
---|
10 |
user output |
---|
10 |
Test 8
Group: 2
Verdict: ACCEPTED
input |
---|
1000 1000 ##############################... |
correct output |
---|
436 |
user output |
---|
436 |
Test 9
Group: 2
Verdict: ACCEPTED
input |
---|
1000 1000 ##############################... |
correct output |
---|
2 |
user output |
---|
2 |
Test 10
Group: 1, 2
Verdict: ACCEPTED
input |
---|
20 20 #################### #B................## #################.## #################.## ... |
correct output |
---|
2 |
user output |
---|
2 |
Test 11
Group: 2
Verdict: ACCEPTED
input |
---|
1000 1000 ##############################... |
correct output |
---|
2 |
user output |
---|
2 |
Test 12
Group: 1, 2
Verdict: ACCEPTED
input |
---|
20 20 #################### ##########A######### ##########.######### ##########.######### ... |
correct output |
---|
2 |
user output |
---|
2 |
Test 13
Group: 2
Verdict: ACCEPTED
input |
---|
1000 1000 ##############################... |
correct output |
---|
2 |
user output |
---|
2 |
Test 14
Group: 1, 2
Verdict: ACCEPTED
input |
---|
20 20 #################### ##########A######### ##########.######### ##########.######### ... |
correct output |
---|
12 |
user output |
---|
12 |
Test 15
Group: 2
Verdict: ACCEPTED
input |
---|
1000 1000 ##############################... |
correct output |
---|
502 |
user output |
---|
502 |
Test 16
Group: 2
Verdict: ACCEPTED
input |
---|
3 1000 ##############################... |
correct output |
---|
1 |
user output |
---|
1 |
Test 17
Group: 2
Verdict: ACCEPTED
input |
---|
1000 3 ### #A# #.# #.# ... |
correct output |
---|
1 |
user output |
---|
1 |