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

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
vector<int> v[1000000];
string p[1000];
bool o[1000000];
bool k[1000000];
int A,B;
ll t=1e9;
ll ite1(int y,int x,ll d){
if(p[y][x]=='A'){
return d;
}
if(d>t)return 1e9;
ll e=1e9;
if(y!=0)e=min(e,ite1(y-1,x,d+1));
if(x!=m-1)e=min(e,ite1(y,x+1,d+1));
return e;
}
ll ite2(int y,int x,ll d){
if(p[y][x]=='A'){
return d;
}
if(d>t)return 1e9;
ll e=1e9;
if(x!=m-1)e=min(e,ite2(y,x+1,d+1));
if(y!=n-1)e=min(e,ite2(y+1,x,d+1));
return e;
}
ll ite3(int y,int x,ll d){
if(p[y][x]=='A'){
return d;
}
if(d>t)return 1e9;
ll e=1e9;
if(y!=n-1)e=min(e,ite3(y+1,x,d+1));
if(x!=0)e=min(e,ite3(y,x-1,d+1));
return e;
}
ll ite4(int y,int x,ll d){
if(p[y][x]=='A'){
return d;
}
if(d>t)return 1e9;
ll e=1e9;
if(x!=0)e=min(e,ite4(y,x-1,d+1));
if(y!=0)e=min(e,ite4(y-1,x,d+1));
return e;
}
void recA(int u){
if(k[u])return;
if(u==B){
cout<<"1\n";
exit(0);
}
k[u]=1;
p[u/m][u%m]='A';
for(auto &i:v[u])recA(i);
}
void recB(int p){
if(k[p])return;
k[p]=1;
t=min(t,ite1(p/m-1,p%m,1));
t=min(t,ite2(p/m,p%m+1,1));
t=min(t,ite3(p/m+1,p%m,1));
t=min(t,ite4(p/m,p%m-1,1));
for(auto &i:v[p]){
recB(i);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n>>m;
for(int i=0;i<n;i++)cin>>p[i];
for(int i=1;i<n-1;i++)for(int j=1;j<m-1;j++){
if(p[i][j]=='.'||p[i][j]=='A'||p[i][j]=='B'){
o[i*m+j]=1;
if(j!=n-1&&p[i][j+1]=='.')v[i*m+j].push_back(i*m+j+1);
if(j!=0&&p[i][j-1]=='.')v[i*m+j].push_back(i*m+j-1);
if(i!=m-1&&p[i+1][j]=='.')v[i*m+j].push_back((i+1)*m+j);
if(i!=0&&p[i-1][j]=='.')v[i*m+j].push_back((i-1)*m+j);
if(p[i][j]=='A')A=i*m+j;
if(p[i][j]=='B')B=i*m+j;
}
}
recA(A);
recB(B);
cout<<t<<"\n";
}

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:

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:

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

correct output
2

user output
(empty)

Test 14

Group: 1, 2

Verdict: ACCEPTED

input
20 20
####################
##########A#########
##########.#########
##########.#########
...

correct output
12

user output
12

Test 15

Group: 2

Verdict:

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

correct output
502

user output
(empty)

Test 16

Group: 2

Verdict: ACCEPTED

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

correct output
1

user output
1

Test 17

Group: 2

Verdict:

input
1000 3
###
#A#
#.#
#.#
...

correct output
1

user output
(empty)