— Dark mode

Datatähti 2026 alku

Hypyt

  • Start: 2025-10-27 00:00:00
  • End: 2025-11-10 00:00:00
Submission details
Task:Hypyt
Sender:lukarantalainen
Submission time:2026-07-13 10:55:58 +0300
Language:C++ (C++20)
Status:READY
Result:0
Feedback
subtaskverdictscore
#10
#20
#30
#40
#50
Test results
testverdicttimesubtask
#10.00 s1, 2, 3, 4, 5details
#20.00 s1, 2, 3, 4, 5details
#30.00 s1, 2, 3, 4, 5details
#40.00 s1, 2, 3, 4, 5details
#50.00 s1, 2, 3, 4, 5details
#60.00 s2, 5details
#70.00 s2, 5details
#80.00 s2, 5details
#90.00 s3, 4, 5details
#100.01 s3, 4, 5details
#110.01 s3, 4, 5details
#120.00 s4, 5details
#130.00 s4, 5details
#140.00 s4, 5details
#150.00 s5details
#160.00 s5details
#170.00 s5details
#180.00 s5details
#190.00 s5details
#200.00 s5details
#210.00 s5details
#220.00 s1, 2, 3, 4, 5details
#230.00 s1, 2, 3, 4, 5details
#240.00 s5details
#250.00 s5details
#260.00 s5details
#270.00 s5details

Compiler report

input/code.cpp: In function 'int find_route(const std::vector<std::__cxx11::basic_string<char> >&, Point, Point)':
input/code.cpp:58:10: warning: unused variable 'valid' [-Wunused-variable]
   58 |     bool valid{};
      |          ^~~~~
In file included from /usr/include/c++/13/cassert:44,
                 from input/code.cpp:1:
input/code.cpp: In function 'int main()':
input/code.cpp:97:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::__cxx11::basic_string<char> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   97 |   assert(grid.size() == n && grid[grid.size() - 1].size() == m);
      |          ~~~~~~~~~~~~^~~~
input/code.cpp:97:59: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   97 |   assert(grid.size() == n && grid[grid.size() - 1].size() == m);
      |                              ~~~~~~~~~~~~~~~~...

Code

#include <cassert>
#include <fstream>
#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>

using namespace std;

struct Point {
  int x;
  int y;

  struct HashFunction {
    size_t operator()(const Point& point) const {
      size_t x_hash = std::hash<int>()(point.x);
      size_t y_hash = std::hash<int>()(point.y);
      return x_hash ^ y_hash;
    }
  };
};

bool operator==(const Point a, const Point b) {
  return (a.x == b.x && a.y == b.y);
}

bool operator!=(const Point a, const Point b) {
  return !(a.x == b.x && a.y == b.y);
}

ostream& operator<<(ostream& out, Point point) {
  out << point.x << "," << point.y;
  return out;
}

// have to find the same column or row as the target
int find_route(const std::vector<std::string>& grid, const Point start, const Point target) {
  const int n = grid.size();
  const int m = grid[0].size();

  queue<std::pair<Point, int>> q;

  q.push({start, 0});

  std::vector<std::vector<bool>> visited(n, std::vector<bool>(m, false));
  
  visited[start.y][start.x] = true;

  while (!q.empty()) {
    auto curr{q.front()};
    q.pop();

    if (curr.first == target) return curr.second;

    bool valid{};
    for (int col{}; col < m; ++col) {
      Point test{col, curr.first.y};
      if (!visited[test.y][test.x] && grid[test.y][test.x] != '*') {
        visited[test.y][test.x] = true;
        q.push({test, curr.second+1});
      }
    }

    for (int row{}; row < n; ++row) {
      Point test{curr.first.x, row};
      if (!visited[test.y][test.x] && grid[test.y][test.x] != '*') {
        visited[test.y][test.x] = true;
        q.push({test, curr.second+1});
      }
    }
  }

  return -1;
}

int main() {
  iostream::ios_base::sync_with_stdio(0);
  ifstream in("in.txt");
  cin.tie(0);
  cin.rdbuf(in.rdbuf());

  int n, m, q;
  cin >> n >> m >> q;

  std::vector<std::string> grid;
  for (int i{}; i < n; ++i) {
    std::string line;
    while (line == "") {
      std::getline(std::cin, line);
    }
    grid.push_back(line);
  }

  assert(grid.size() == n && grid[grid.size() - 1].size() == m);

  for (int i{}; i < q; ++i) {
    Point start;
    Point target;

    std::cin >> start.y >> start.x >> target.y >> target.x;
    --start.x;
    --start.y;
    --target.x;
    --target.y;

    int result = find_route(grid, start, target);
    std::cout << result << "\n";
  }

  return 0;
}

Test details

Test 1 (public)

Subtask: 1, 2, 3, 4, 5

Verdict:

input
4 6 5
.*.***
*...**
*****.
*..*.*
...
view save

correct output
1
0
3
3
-1
view save

user output
(empty)

Test 2

Subtask: 1, 2, 3, 4, 5

Verdict:

input
10 10 10
..........
.....*....
........*.
*.*....*..
...
view save

correct output
1
2
1
2
2
...
view save

user output
(empty)

Test 3

Subtask: 1, 2, 3, 4, 5

Verdict:

input
10 10 10
*...***.**
*****.*...
**..**.**.
..**.**.*.
...
view save

correct output
1
2
2
1
2
...
view save

user output
(empty)

Test 4

Subtask: 1, 2, 3, 4, 5

Verdict:

input
10 10 10
***.*.****
**********
*.********
.*.***.**.
...
view save

correct output
3
4
2
3
4
...
view save

user output
(empty)

Test 5

Subtask: 1, 2, 3, 4, 5

Verdict:

input
10 10 1
.****.****
**.**..***
**********
*******..*
...
view save

correct output
7
view save

user output
(empty)

Test 6

Subtask: 2, 5

Verdict:

input
250 250 250
.*...*.....*******..**...*.......
view save

correct output
2
3
3
2
2
...
view save

user output
(empty)

Test 7

Subtask: 2, 5

Verdict:

input
250 250 250
...*......**.**.*.*..**..*..**...
view save

correct output
2
2
2
2
3
...
view save

user output
(empty)

Test 8

Subtask: 2, 5

Verdict:

input
250 250 250
**..**..****.****.*.***.***..*...
view save

correct output
2
3
3
3
3
...
view save

user output
(empty)

Test 9

Subtask: 3, 4, 5

Verdict:

input
40 40 200000
...*.**.*..*.............*.*.....
view save

correct output
2
2
2
2
2
...
view save

user output
(empty)

Test 10

Subtask: 3, 4, 5

Verdict:

input
40 40 200000
**.**..*.*.*.******....****.*....
view save

correct output
2
1
3
2
2
...
view save

user output
(empty)

Test 11

Subtask: 3, 4, 5

Verdict:

input
40 40 200000
.*.*.**.*****.***.*.****.**.**...
view save

correct output
3
3
3
3
3
...
view save

user output
(empty)

Test 12

Subtask: 4, 5

Verdict:

input
80 80 200000
*....**.***..****...*.....*......
view save

correct output
2
2
2
2
2
...
view save

user output
(empty)

Test 13

Subtask: 4, 5

Verdict:

input
80 80 200000
.***.*..*.***..*****....**...*...
view save

correct output
3
2
2
3
2
...
view save

user output
(empty)

Test 14

Subtask: 4, 5

Verdict:

input
80 80 200000
*******.*****.*..*..****...***...
view save

correct output
2
3
1
2
2
...
view save

user output
(empty)

Test 15

Subtask: 5

Verdict:

input
250 250 200000
*....*..*..*..**..*.........**...
view save

correct output
3
2
2
2
2
...
view save

user output
(empty)

Test 16

Subtask: 5

Verdict:

input
250 250 200000
..*....*..*......*.**.*.*..***...
view save

correct output
2
2
2
2
2
...
view save

user output
(empty)

Test 17

Subtask: 5

Verdict:

input
250 250 200000
*..*.*****.*********.****.****...
view save

correct output
3
3
2
2
2
...
view save

user output
(empty)

Test 18

Subtask: 5

Verdict:

input
250 250 200000
*********.**********.******.**...
view save

correct output
3
3
3
3
3
...
view save

user output
(empty)

Test 19

Subtask: 5

Verdict:

input
250 250 200000
.*****************************...
view save

correct output
104
422
145
93
65
...
view save

user output
(empty)

Test 20

Subtask: 5

Verdict:

input
250 250 200000
..****************************...
view save

correct output
57
155
38
65
98
...
view save

user output
(empty)

Test 21

Subtask: 5

Verdict:

input
250 250 200000
.*****************************...
view save

correct output
498
498
498
498
498
...
view save

user output
(empty)

Test 22

Subtask: 1, 2, 3, 4, 5

Verdict:

input
10 1 10
*
*
.
*
...
view save

correct output
0
1
1
0
0
...
view save

user output
(empty)

Test 23

Subtask: 1, 2, 3, 4, 5

Verdict:

input
1 10 10
........*.
1 7 1 10
1 4 1 7
1 5 1 1
...
view save

correct output
1
1
1
1
1
...
view save

user output
(empty)

Test 24

Subtask: 5

Verdict:

input
250 1 200000
*
.
*
.
...
view save

correct output
1
1
1
1
1
...
view save

user output
(empty)

Test 25

Subtask: 5

Verdict:

input
1 250 200000
*.*.*...*.*.**.***..**.*.*..**...
view save

correct output
1
1
1
1
1
...
view save

user output
(empty)

Test 26

Subtask: 5

Verdict:

input
250 250 200000
.................................
view save

correct output
2
2
2
2
2
...
view save

user output
(empty)

Test 27

Subtask: 5

Verdict:

input
250 250 200000
******************************...
view save

correct output
0
0
0
0
0
...
view save

user output
(empty)

Tasks

A Palindromi-B Monikulmio-C Tulkki-D Maalaus-E Hypyt-F Lukujono-

Submissions (lukarantalainen)

2026-07-19 10:36:55 302026-07-19 10:31:53 302026-07-19 10:27:44 302026-07-19 10:24:39 302026-07-19 10:20:23 102026-07-19 10:02:51 02026-07-13 11:54:33 02026-07-13 11:52:03 02026-07-13 11:37:49 02026-07-13 11:36:16 02026-07-13 10:58:11 102026-07-13 10:55:58 02026-07-04 16:26:03 0