Task: | Sokkelo |
Sender: | tonero |
Submission time: | 2022-01-22 16:41:41 +0200 |
Language: | C++ (C++17) |
Status: | READY |
Result: | 28 |
group | verdict | score |
---|---|---|
#1 | ACCEPTED | 28 |
#2 | TIME LIMIT EXCEEDED | 0 |
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 | TIME LIMIT EXCEEDED | -- | 2 | details |
#5 | TIME LIMIT EXCEEDED | -- | 2 | details |
#6 | TIME LIMIT EXCEEDED | -- | 2 | details |
#7 | ACCEPTED | 0.01 s | 1, 2 | details |
#8 | TIME LIMIT EXCEEDED | -- | 2 | details |
#9 | TIME LIMIT EXCEEDED | -- | 2 | details |
#10 | ACCEPTED | 0.01 s | 1, 2 | details |
#11 | TIME LIMIT EXCEEDED | -- | 2 | details |
#12 | ACCEPTED | 0.01 s | 1, 2 | details |
#13 | ACCEPTED | 0.02 s | 2 | details |
#14 | ACCEPTED | 0.01 s | 1, 2 | details |
#15 | ACCEPTED | 0.02 s | 2 | details |
#16 | ACCEPTED | 0.01 s | 2 | details |
#17 | ACCEPTED | 0.01 s | 2 | details |
Code
#include <bits/stdc++.h>using namespace std;#define ull unsigned long long#define ll long longvector<pair<int,int>> p1;vector<pair<int,int>> p2;int n,m;char ma[1001][1001];bool v[1001][1001] {false};bool v2[1001][1001] {false};int main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);cin >> n >> m;deque<pair<int,int>> vec;int a1,a2,s1,s2;for (int i = 1; i <= n; ++i){for (int u = 1; u <= m; ++u){cin >> ma[i][u];if(ma[i][u] == 'A'){a1 = i;a2 = u;}else if(ma[i][u] == 'B'){s1 = i;s2 = u;}}}vec.emplace_back(a1,a2);while(!vec.empty()){auto top = vec.front();vec.pop_front();if(top.first != n && !v[top.first+1][top.second] && ma[top.first+1][top.second] != '#'){p1.emplace_back(top.first+1,top.second);v[top.first+1][top.second] = true;vec.emplace_back(top.first+1, top.second);}if(top.first != 1 && !v[top.first-1][top.second] && ma[top.first-1][top.second] != '#'){p1.emplace_back(top.first-1,top.second);v[top.first-1][top.second] = true;vec.emplace_back(top.first-1, top.second);}if(top.second != m && !v[top.first][top.second+1] && ma[top.first][top.second+1] != '#'){p1.emplace_back(top.first,top.second+1);v[top.first][top.second+1] = true;vec.emplace_back(top.first, top.second+1);}if(top.second != 1 && !v[top.first][top.second-1] && ma[top.first][top.second-1] != '#'){p1.emplace_back(top.first,top.second-1);v[top.first][top.second-1] = true;vec.emplace_back(top.first, top.second-1);}}vec.emplace_back(s1, s2);while(!vec.empty()){auto top = vec.front();vec.pop_front();if(top.first != n && !v2[top.first+1][top.second] && ma[top.first+1][top.second] != '#'){p2.emplace_back(top.first+1,top.second);v2[top.first+1][top.second] = true;vec.emplace_back(top.first+1, top.second);}if(top.first != 1 && !v2[top.first-1][top.second] && ma[top.first-1][top.second] != '#'){p2.emplace_back(top.first-1,top.second);v2[top.first-1][top.second] = true;vec.emplace_back(top.first-1, top.second);}if(top.second != m && !v2[top.first][top.second+1] && ma[top.first][top.second+1] != '#'){p2.emplace_back(top.first,top.second+1);v2[top.first][top.second+1] = true;vec.emplace_back(top.first, top.second+1);}if(top.second != 1 && !v2[top.first][top.second-1] && ma[top.first][top.second-1] != '#'){p2.emplace_back(top.first,top.second-1);v2[top.first][top.second-1] = true;vec.emplace_back(top.first, top.second-1);}}int mi = INT32_MAX;for (const auto &item : p1){for (const auto &item2 : p2){mi = min(abs(item.first-item2.first) + abs(item.second-item2.second), mi);}}if(mi < 1) mi = 1;cout << mi;flush(std::cout);}
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: TIME LIMIT EXCEEDED
input |
---|
1000 1000 ##############################... |
correct output |
---|
1 |
user output |
---|
(empty) |
Test 5
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 1000 ##############################... |
correct output |
---|
2 |
user output |
---|
(empty) |
Test 6
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 1000 ##############################... |
correct output |
---|
335 |
user output |
---|
(empty) |
Test 7
Group: 1, 2
Verdict: ACCEPTED
input |
---|
20 20 #################### #####.############## ###.....############ ##.......########### ... |
correct output |
---|
10 |
user output |
---|
10 |
Test 8
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 1000 ##############################... |
correct output |
---|
436 |
user output |
---|
(empty) |
Test 9
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 1000 ##############################... |
correct output |
---|
2 |
user output |
---|
(empty) |
Test 10
Group: 1, 2
Verdict: ACCEPTED
input |
---|
20 20 #################### #B................## #################.## #################.## ... |
correct output |
---|
2 |
user output |
---|
2 |
Test 11
Group: 2
Verdict: TIME LIMIT EXCEEDED
input |
---|
1000 1000 ##############################... |
correct output |
---|
2 |
user output |
---|
(empty) |
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 |