CSES - Datatähti 2025 loppu

Submission details
Task:	Suunnistus
Sender:	MikaelM
Submission time:	2025-01-18 14:06:17 +0200
Language:	C++ (C++17)
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.00 s	3	details
#2	ACCEPTED	0.01 s	1, 2, 3	details
#3	ACCEPTED	0.01 s	1, 2, 3	details
#4	ACCEPTED	0.01 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.06 s	2, 3	details
#8	ACCEPTED	0.07 s	2, 3	details
#9	ACCEPTED	0.01 s	2, 3	details
#10	ACCEPTED	0.12 s	3	details
#11	ACCEPTED	0.14 s	3	details
#12	ACCEPTED	0.03 s	3	details
#13	ACCEPTED	0.10 s	3	details
#14	ACCEPTED	0.04 s	2, 3	details
#15	ACCEPTED	0.01 s	3	details
#16	ACCEPTED	0.00 s	3	details
#17	ACCEPTED	0.02 s	2, 3	details

Code

#include<bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
using ll = long long;

char c[501][501];
vector<pair<int, int>> rastit[10];
int e[15][500][500];

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    int n, m, k;
    cin >> n >> m >> k;

    pair<int, int> start, end;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> c[i][j];
            if (c[i][j] >= '1' && c[i][j] <= '9') rastit[c[i][j] - '1' + 1].push_back({i, j});
            else if (c[i][j] == 'S') start = {i, j};
            else if (c[i][j] == 'E') end = {i, j};
        }
    }


    // S

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            e[0][i][j] = 1e9;
        }
    }
    e[0][start.first][start.second] = 0;

    queue<pair<int, int>> q;
    q.push({start.first, start.second});


    while (!q.empty()) {
        int y = q.front().first, x = q.front().second;
        q.pop();

        if (y > 1 && c[y-1][x] != '#' && e[0][y][x] + 1 < e[0][y-1][x]) {
            e[0][y-1][x] = e[0][y][x] + 1;
            q.push({y-1, x});
        }
        if (y < n && c[y+1][x] != '#' && e[0][y][x] + 1 < e[0][y+1][x]) {
            e[0][y+1][x] = e[0][y][x] + 1;
            q.push({y+1, x});
        }
        if (x > 0 && c[y][x-1] != '#' && e[0][y][x] + 1 < e[0][y][x-1]) {
            e[0][y][x-1] = e[0][y][x] + 1;
            q.push({y, x-1});
        }
        if (x < m && c[y][x+1] != '#' && e[0][y][x] + 1 < e[0][y][x+1]) {
            e[0][y][x+1] = e[0][y][x] + 1;
            q.push({y, x+1});
        } 

    }  

    // for (int i = 1; i <= n; i++) {
    //     for (int j = 1; j <= m; j++) {
    //         if (e[0][i][j] == 1e9) {
    //             cout << 0;
    //         }
    //         else cout << e[0][i][j];
    //     }
    //     cout << "\n";
    // }



    // rastit

    for (int r = 1; r <= k; r++) {

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                e[r][i][j] = 1e9;
            }
        }

        queue<pair<int, int>> q;
        for (auto u : rastit[r]) {
            e[r][u.first][u.second] = e[r-1][u.first][u.second];
            q.push({u.first, u.second});
        }




        while (!q.empty()) {
            int y = q.front().first, x = q.front().second;
            q.pop();

            if (y > 1 && c[y-1][x] != '#' && e[r][y][x] + 1 < e[r][y-1][x]) {
                e[r][y-1][x] = e[r][y][x] + 1;
                q.push({y-1, x});
            }
            if (y < n && c[y+1][x] != '#' && e[r][y][x] + 1 < e[r][y+1][x]) {
                e[r][y+1][x] = e[r][y][x] + 1;
                q.push({y+1, x});
            }
            if (x > 0 && c[y][x-1] != '#' && e[r][y][x] + 1 < e[r][y][x-1]) {
                e[r][y][x-1] = e[r][y][x] + 1;
                q.push({y, x-1});
            }
            if (x < m && c[y][x+1] != '#' && e[r][y][x] + 1 < e[r][y][x+1]) {
                e[r][y][x+1] = e[r][y][x] + 1;
                q.push({y, x+1});
            } 

        }  


            

    }

    cout << (e[k][end.first][end.second] == 1e9 ? -1 : e[k][end.first][end.second]);


}

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 (MikaelM)