CSES - Datatähti 2022 loppu - Results
Submission details
Task:Sokkelo
Sender:tonero
Submission time:2022-01-22 16:41:41 +0200
Language:C++ (C++17)
Status:READY
Result:28
Feedback
groupverdictscore
#1ACCEPTED28
#20
Test results
testverdicttimegroup
#1ACCEPTED0.01 s1, 2details
#2ACCEPTED0.01 s1, 2details
#3ACCEPTED0.01 s1, 2details
#4--2details
#5--2details
#6--2details
#7ACCEPTED0.01 s1, 2details
#8--2details
#9--2details
#10ACCEPTED0.01 s1, 2details
#11--2details
#12ACCEPTED0.01 s1, 2details
#13ACCEPTED0.02 s2details
#14ACCEPTED0.01 s1, 2details
#15ACCEPTED0.02 s2details
#16ACCEPTED0.01 s2details
#17ACCEPTED0.01 s2details

Code

#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
vector<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:

input
1000 1000
##############################...

correct output
1

user output
(empty)

Test 5

Group: 2

Verdict:

input
1000 1000
##############################...

correct output
2

user output
(empty)

Test 6

Group: 2

Verdict:

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:

input
1000 1000
##############################...

correct output
436

user output
(empty)

Test 9

Group: 2

Verdict:

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:

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