CSES - Datatähti 2025 loppu

Submission details
Task:	Suunnistus
Sender:	Verlet
Submission time:	2025-01-19 10:41:25 +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.04 s	1, 2, 3	details
#3	ACCEPTED	0.03 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.01 s	1, 2, 3	details
#7	ACCEPTED	0.15 s	2, 3	details
#8	ACCEPTED	0.17 s	2, 3	details
#9	ACCEPTED	0.02 s	2, 3	details
#10	ACCEPTED	0.04 s	3	details
#11	ACCEPTED	0.05 s	3	details
#12	ACCEPTED	0.02 s	3	details
#13	ACCEPTED	0.17 s	3	details
#14	ACCEPTED	0.09 s	2, 3	details
#15	ACCEPTED	0.00 s	3	details
#16	ACCEPTED	0.01 s	3	details
#17	ACCEPTED	0.04 s	2, 3	details

Code

#include <bits/stdc++.h>

#define N 502

#define F first
#define S second

#define pb push_back

using namespace std;

typedef pair<int, int> ip;

struct Move
{
  ip p;
  int d;
  int t;
};

char m[N][N];
char v[N][N][10];

int bfs(Move start, vector<char> targets)
{
  queue<Move> q;

  q.push(start);

  while (q.size())
  {
    Move n = q.front(); q.pop();

    int t = n.t;
    int d = n.d;
    int x = n.p.F;
    int y = n.p.S;

    if (v[x][y][t] || m[x][y] == '#') continue;

    v[x][y][t] = true;

    if (m[x][y] == targets[t])
    {
      if (targets[t] == targets.back()) return d;
      
      q.push({{x, y}, d, t+1});

      continue;
    }

    q.push({{x+1, y}, d+1, t});
    q.push({{x-1, y}, d+1, t});
    q.push({{x, y+1}, d+1, t});
    q.push({{x, y-1}, d+1, t});
  }

  return -1;
}

int main()
{
  int w, h, k; cin >> h >> w >> k;

  for (int y = 0; y < N; y++)
  for (int x = 0; x < N; x++)
  {
    m[x][y] = '#';
  }

  ip start;

  // cout << "Width: " << w << endl;
  // cout << "Height: " << h << endl;

  for (int y = 1; y <= h; y++)
  for (int x = 1; x <= w; x++)
  {
    char c; cin >> c;

    if (c != '#') m[x][y] = c;

    if (c == 'S') start = {x, y};
  }

  // cout << "Start: " << s.F << " " << s.S << endl;
  // cout << "End: " << e.F << " " << e.S << endl;

  // for (int y = 0; y <= h + 1; y++)
  // {
  //   for (int x = 0; x <= w + 1; x++)
  //   {
  //     cout << m[x][y] << " ";
  //   }
  //   cout << endl;
  // }

  vector<char> targets;

  for (char c = '1'; c < '1' + k; c++)
    targets.pb(c);
  
  targets.pb('E');

  cout << bfs({start, 0, 0}, targets) << endl;
}

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