CSES - Datatähti 2025 loppu

Submission details
Task:	Suunnistus
Sender:	maweiyin24562
Submission time:	2025-01-18 14:29:46 +0200
Language:	C++ (C++11)
Status:	READY
Result:	100

Feedback
group	verdict	score
#1	ACCEPTED	31
#2	ACCEPTED	12
#3	ACCEPTED	57

Test results
test	verdict	time	group
#1	ACCEPTED	0.01 s	3	details
#2	ACCEPTED	0.02 s	1, 2, 3	details
#3	ACCEPTED	0.02 s	1, 2, 3	details
#4	ACCEPTED	0.02 s	1, 2, 3	details
#5	ACCEPTED	0.00 s	1, 2, 3	details
#6	ACCEPTED	0.00 s	1, 2, 3	details
#7	ACCEPTED	0.15 s	2, 3	details
#8	ACCEPTED	0.15 s	2, 3	details
#9	ACCEPTED	0.02 s	2, 3	details
#10	ACCEPTED	0.80 s	3	details
#11	ACCEPTED	0.80 s	3	details
#12	ACCEPTED	0.02 s	3	details
#13	ACCEPTED	0.55 s	3	details
#14	ACCEPTED	0.06 s	2, 3	details
#15	ACCEPTED	0.01 s	3	details
#16	ACCEPTED	0.01 s	3	details
#17	ACCEPTED	0.04 s	2, 3	details

Code

#include <bits/stdc++.h>

#define ll long long
#define lbit(u) (u&(-u))

const int N=100009;

using namespace std;

char mp[509][509];
int d[509][509];
int n,m,sx,sy;
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};

struct Node{
    int x,y,d;
};

int k;

bool islegal(int x,int y){
    return mp[x][y]!='#'&&x>=1&&x<=n&&y>=1&&y<=m;
}
queue<Node>q;
queue<Node>q_new;
queue<Node>q_empty;
void bfsnopatrol(){
    q.push({sx,sy,0});
    d[sx][sy]=1;
    while(!q.empty()){
        Node now=q.front();
        q.pop();
        if(mp[now.x][now.y]=='E'){
            cout<<now.d<<endl;
            return;
        }
        for(int i=0;i<4;i++){
            int nx=now.x+dx[i];
            int ny=now.y+dy[i];
            if(islegal(nx,ny)&&d[nx][ny]!=1){
                q.push({nx,ny,now.d+1});
                d[nx][ny]=1;
            }
        }
    }
    cout<<-1<<endl;
}

void bfs(){
    q_new.push({sx,sy,0});
    for(int i=1;i<=k;i++){
        q=q_new;
        q_new=q_empty;
        memset(d,0x7f7f7f,sizeof(d));
        while(!q.empty()){
            Node now=q.front();
            q.pop();
            if(d[now.x][now.y]<=now.d)continue;
            d[now.x][now.y]=now.d;
            if(mp[now.x][now.y]==i+'0'){
                q_new.push(now);
            }
            for(int i=0;i<4;i++){
                int nx=now.x+dx[i];
                int ny=now.y+dy[i];
                if(islegal(nx,ny)){
                    q.push({nx,ny,now.d+1});
                }
            }
        }
    }
    q=q_new;
    q_new=q_empty;
    int ans=0x7f7f7f;
    memset(d,0x7f7f7f,sizeof(d));
    while(!q.empty()){
        Node now=q.front();
        q.pop();
        if(d[now.x][now.y]<=now.d)continue;
        d[now.x][now.y]=now.d;
        if(mp[now.x][now.y]=='E'){
            ans=min(ans,now.d);
            continue;
        }
        for(int i=0;i<4;i++){
            int nx=now.x+dx[i];
            int ny=now.y+dy[i];
            if(islegal(nx,ny)){
                q.push({nx,ny,now.d+1});
            }
        }
    }
    if(ans==0x7f7f7f)cout<<-1<<endl;
    else cout<<ans<<endl;
}

int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            cin>>mp[i][j];
            if(mp[i][j]=='S'){sx=i;sy=j;}
        }
    if(k==0)bfsnopatrol();
    else bfs();
    return 0;
}

/*

*/

Test details

Test 1

Group: 3

Verdict: ACCEPTED

input
`10 10 9 S293#35616 #662963731 54975451#7 5162589168 ...` view save

correct output
`25` view save

user output
`25` view save

Test 2

Group: 1, 2, 3

Verdict: ACCEPTED

input
`500 500 0 .................................` view save

correct output
`301` view save

user output
`301` view save

Test 3

Group: 1, 2, 3

Verdict: ACCEPTED

input
`500 500 0 .#.........#.#..##..#............` view save

correct output
`253` view save

user output
`253` view save

Test 4

Group: 1, 2, 3

Verdict: ACCEPTED

input
`500 500 0 ...#......##.##.#.#..##..#..##...` view save

correct output
`-1` view save

user output
`-1` view save

Test 5

Group: 1, 2, 3

Verdict: ACCEPTED

input
`500 1 0 . . . . ...` view save

correct output
`77` view save

user output
`77` view save

Test 6

Group: 1, 2, 3

Verdict: ACCEPTED

input
`1 500 0 .................................` view save

correct output
`166` view save

user output
`166` view save

Test 7

Group: 2, 3

Verdict: ACCEPTED

input
`500 500 9 .................................` view save

correct output
`3447` view save

user output
`3447` view save

Test 8

Group: 2, 3

Verdict: ACCEPTED

input
`500 500 9 .#........#..................#...` view save

correct output
`4952` view save

user output
`4952` view save

Test 9

Group: 2, 3

Verdict: ACCEPTED

input
`500 500 9 ##.########.##########.#..#......` view save

correct output
`-1` view save

user output
`-1` view save

Test 10

Group: 3

Verdict: ACCEPTED

input
`500 500 9 623475428948841896621266296765...` view save

correct output
`205` view save

user output
`205` view save

Test 11

Group: 3

Verdict: ACCEPTED

input
`500 500 9 7##814125813#3463#272134469457...` view save

correct output
`157` view save

user output
`157` view save

Test 12

Group: 3

Verdict: ACCEPTED

input
`500 500 9 ##67##36##5#3###67###8972#61##...` view save

correct output
`-1` view save

user output
`-1` view save

Test 13

Group: 3

Verdict: ACCEPTED

input
`500 500 9 ....................#...#........` view save

correct output
`1313` view save

user output
`1313` view save

Test 14

Group: 2, 3

Verdict: ACCEPTED

input
`499 499 9 S#...#...#...#...#...#...#...#...` view save

correct output
`1124942` view save

user output
`1124942` view save

Test 15

Group: 3

Verdict: ACCEPTED

input
`500 1 9 1 6 1 3 ...` view save

correct output
`332` view save

user output
`332` view save

Test 16

Group: 3

Verdict: ACCEPTED

input
`1 500 9 996327784392827829434482995353...` view save

correct output
`135` view save

user output
`135` view save

Test 17

Group: 2, 3

Verdict: ACCEPTED

input
`500 500 9 .................................` view save

correct output
`-1` view save

user output
`-1` view save

Datatähti 2025 loppu

Suunnistus

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Tasks

Submissions (maweiyin24562)