— 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:JuusoH
Submission time:2025-11-06 19:07:48 +0200
Language:Rust (2021)
Status:READY
Result:0
Feedback
groupverdictscore
#10
#20
#30
#40
#50
Test results
testverdicttimegroup
#10.00 s1, 2, 3, 4, 5details
#2ACCEPTED0.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
#6ACCEPTED0.00 s2, 5details
#70.00 s2, 5details
#80.00 s2, 5details
#90.04 s3, 4, 5details
#100.04 s3, 4, 5details
#110.04 s3, 4, 5details
#120.04 s4, 5details
#130.04 s4, 5details
#140.04 s4, 5details
#150.04 s5details
#160.04 s5details
#170.04 s5details
#180.04 s5details
#190.08 s5details
#200.07 s5details
#21--5details
#22ACCEPTED0.00 s1, 2, 3, 4, 5details
#23ACCEPTED0.00 s1, 2, 3, 4, 5details
#24ACCEPTED0.31 s5details
#25ACCEPTED0.31 s5details
#26ACCEPTED0.31 s5details
#27ACCEPTED0.31 s5details

Compiler report

warning: unused import: `std::collections::VecDeque`
 --> input/code.rs:1:5
  |
1 | use std::collections::VecDeque;
  |     ^^^^^^^^^^^^^^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unused import: `std::time`
 --> input/code.rs:3:5
  |
3 | use std::time;
  |     ^^^^^^^^^

warning: unused import: `std::time::*`
 --> input/code.rs:4:5
  |
4 | use std::time::*;
  |     ^^^^^^^^^^^^

warning: 3 warnings emitted

Code

use std::collections::VecDeque;
use std::io;
use std::time;
use std::time::*;
type Pos = (usize, usize);
fn main() {
    let mut input = String::new();
    let stdin = io::stdin();
    _ = stdin.read_line(&mut input);
    let mut first_line = input.split_whitespace();
    let n: usize = first_line.next().unwrap().parse().unwrap();
    let m: usize = first_line.next().unwrap().parse().unwrap();
    let q: usize = first_line.next().unwrap().parse().unwrap();

    let mut board: [[bool; 250]; 250] = [[false; 250]; 250];

    for i in 0..n {
        input.clear();
        _ = stdin.read_line(&mut input);
        let mut line = input.chars();

        for l in 0..m {
            board[i][l] = line.next().unwrap() == '*';
        }
    }

    let mut tests: Vec<(usize, usize, usize, usize)> = vec![];

    for _ in 0..q {
        input.clear();
        _ = stdin.read_line(&mut input);
        let mut line = input.split_whitespace();
        let y1: usize = line.next().unwrap().parse().unwrap();
        let x1: usize = line.next().unwrap().parse().unwrap();
        let y2: usize = line.next().unwrap().parse().unwrap();
        let x2: usize = line.next().unwrap().parse().unwrap();
        tests.push((y1 - 1, x1 - 1, y2 - 1, x2 - 1));
    }
    // let start_time = SystemTime::now();

    // for i in 0..(2 * 10usize.pow(5)) {
    for t in &tests {
        let start = (t.0, t.1);
        let end = (t.2, t.3);

        let res = breadth_first(&board, start, end, n, m);

        // if i % 100 == 0 {
        //     let dur = SystemTime::now().duration_since(start_time);
        //     println!(
        //         "{} iter per second",
        //         (i as f32 / dur.unwrap().as_secs_f32()).round()
        //     );
        // }

        println!("{res}");
    }
    // }
    // let dur = SystemTime::now().duration_since(start_time);
    // println!("{:?}", dur.unwrap());
}

fn breadth_first(board: &[[bool; 250]; 250], start: Pos, end: Pos, n: usize, m: usize) -> i32 {
    if start == end {
        return 0;
    }
    if one_jump_gap(&start, &end) {
        return 1;
    }
    if two_jump_gap(board, &start, &end) {
        return 2;
    }

    let mut cells: Vec<Pos> = vec![start];

    /*let mut rows: [bool; 250] = [false; 250];
    let mut cols: [bool; 250] = [false; 250];*/
    let mut rows: Vec<usize> = (0..n).collect();
    let mut cols: Vec<usize> = (0..m).collect();

    if start.0 > end.0 {
        rows.swap_remove(start.0);
        rows.swap_remove(end.0);
    } else if start.0 < end.0 {
        rows.swap_remove(end.0);
        rows.swap_remove(start.0);
    } else {
        rows.swap_remove(start.0);
    }

    if start.1 > end.1 {
        cols.swap_remove(start.1);
        cols.swap_remove(end.1);
    } else if start.1 < end.1 {
        cols.swap_remove(end.1);
        cols.swap_remove(start.1);
    } else {
        cols.swap_remove(start.1);
    }

    rows.swap_remove(start.0);
    cols.swap_remove(start.1);
    if start.0 != end.0 {
        if end.0 + 1 >= rows.len() {
            rows.swap_remove(start.0);
        } else {
            rows.swap_remove(end.0);
        }
    }
    if start.1 != end.1 {
        if end.1 + 1 >= cols.len() {
            cols.swap_remove(start.1);
        } else {
            cols.swap_remove(end.1);
        }
    }

    let mut jumps = 1;

    while cells.len() > 0 {
        //let mut new_cells: Vec<Pos> = vec![];
        let cell_len = cells.len();
        for l in (0..cell_len).rev() {
            let cell = cells.swap_remove(l);

            let len = rows.len();
            for i in (0..len).rev() {
                let row = rows[i];
                if !board[row][cell.1] {
                    let new_cell = (row, cell.1);
                    //println!("{new_cell:?}");
                    if two_jump_gap(board, &new_cell, &end) {
                        return jumps + 2;
                    }
                    rows.swap_remove(i);
                    cells.push(new_cell);
                    //removed += 1;
                    //cols[cell.1] = true;
                }
            }
            let len = cols.len();
            //removed = 0;
            for i in (0..len).rev() {
                let col = cols[i];
                if !board[cell.0][col] {
                    let new_cell = (cell.0, col);
                    //println!("{new_cell:?}");
                    if two_jump_gap(board, &new_cell, &end) {
                        return jumps + 2;
                    }
                    //rows[cell.0] = true;
                    cols.swap_remove(i);
                    cells.push(new_cell);
                    //removed += 1;
                }
            }
        }

        //cells = new_cells;
        jumps += 1;
        //println!("{:?}", cells);
    }

    -1
}

fn one_jump_gap(a: &Pos, b: &Pos) -> bool {
    a.0 == b.0 || a.1 == b.1
}

fn two_jump_gap(board: &[[bool; 250]; 250], a: &Pos, b: &Pos) -> bool {
    !board[a.0][b.1] || !board[b.0][a.1]
}

Test details

Test 1 (public)

Group: 1, 2, 3, 4, 5

Verdict:

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

correct output
1
0
3
3
-1
view save

user output
1
0
3
view save

Error:
thread 'main' panicked at /build/rustc-kAv1jW/rustc-1.75.0+dfsg0ubuntu1~bpo0/library/alloc/src/vec/mod.rs:1458:13:
swap_remove index (is 3) should be < len (is 2)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 2

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

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

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

user output
1
2
1
2
2
...
view save

Test 3

Group: 1, 2, 3, 4, 5

Verdict:

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

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

user output
1
2
2
1
2
...
view save

Error:
thread 'main' panicked at /build/rustc-kAv1jW/rustc-1.75.0+dfsg0ubuntu1~bpo0/library/alloc/src/vec/mod.rs:1458:13:
swap_remove index (is 8) should be < len (is 8)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 4

Group: 1, 2, 3, 4, 5

Verdict:

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

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

user output
(empty)

Error:
thread 'main' panicked at /build/rustc-kAv1jW/rustc-1.75.0+dfsg0ubuntu1~bpo0/library/alloc/src/vec/mod.rs:1458:13:
swap_remove index (is 7) should be < len (is 7)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 5

Group: 1, 2, 3, 4, 5

Verdict:

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

correct output
7
view save

user output
-1
view save

Feedback: Incorrect character on line 1 col 1: expected "7", got "-1"

Test 6

Group: 2, 5

Verdict: ACCEPTED

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

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

user output
2
3
3
2
2
...
view save

Test 7

Group: 2, 5

Verdict:

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

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

user output
2
2
2
2
3
...
view save

Error:
thread 'main' panicked at /build/rustc-kAv1jW/rustc-1.75.0+dfsg0ubuntu1~bpo0/library/alloc/src/vec/mod.rs:1458:13:
swap_remove index (is 249) should be < len (is 248)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 8

Group: 2, 5

Verdict:

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

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

user output
2
3
3
3
3
...
view save

Error:
thread 'main' panicked at /build/rustc-kAv1jW/rustc-1.75.0+dfsg0ubuntu1~bpo0/library/alloc/src/vec/mod.rs:1458:13:
swap_remove index (is 248) should be < len (is 248)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 9

Group: 3, 4, 5

Verdict:

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

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

user output
2
2
2
2
2
...
view save

Error:
thread 'main' panicked at /build/rustc-kAv1jW/rustc-1.75.0+dfsg0ubuntu1~bpo0/library/alloc/src/vec/mod.rs:1458:13:
swap_remove index (is 39) should be < len (is 38)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 10

Group: 3, 4, 5

Verdict:

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

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

user output
2
1
3
2
2
...
view save

Error:
thread 'main' panicked at /build/rustc-kAv1jW/rustc-1.75.0+dfsg0ubuntu1~bpo0/library/alloc/src/vec/mod.rs:1458:13:
swap_remove index (is 38) should be < len (is 38)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 11

Group: 3, 4, 5

Verdict:

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

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

user output
3
3
3
view save

Error:
thread 'main' panicked at /build/rustc-kAv1jW/rustc-1.75.0+dfsg0ubuntu1~bpo0/library/alloc/src/vec/mod.rs:1458:13:
swap_remove index (is 37) should be < len (is 37)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 12

Group: 4, 5

Verdict:

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

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

user output
2
2
2
2
2
...
view save

Error:
thread 'main' panicked at /build/rustc-kAv1jW/rustc-1.75.0+dfsg0ubuntu1~bpo0/library/alloc/src/vec/mod.rs:1458:13:
swap_remove index (is 79) should be < len (is 78)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 13

Group: 4, 5

Verdict:

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

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

user output
3
2
2
3
2
...
view save

Error:
thread 'main' panicked at /build/rustc-kAv1jW/rustc-1.75.0+dfsg0ubuntu1~bpo0/library/alloc/src/vec/mod.rs:1458:13:
swap_remove index (is 78) should be < len (is 78)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 14

Group: 4, 5

Verdict:

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

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

user output
2
3
1
2
2
...
view save

Error:
thread 'main' panicked at /build/rustc-kAv1jW/rustc-1.75.0+dfsg0ubuntu1~bpo0/library/alloc/src/vec/mod.rs:1458:13:
swap_remove index (is 79) should be < len (is 78)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 15

Group: 5

Verdict:

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

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

user output
3
2
2
2
2
...
view save

Error:
thread 'main' panicked at /build/rustc-kAv1jW/rustc-1.75.0+dfsg0ubuntu1~bpo0/library/alloc/src/vec/mod.rs:1458:13:
swap_remove index (is 248) should be < len (is 248)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 16

Group: 5

Verdict:

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

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

user output
2
2
2
2
2
...
view save

Error:
thread 'main' panicked at /build/rustc-kAv1jW/rustc-1.75.0+dfsg0ubuntu1~bpo0/library/alloc/src/vec/mod.rs:1458:13:
swap_remove index (is 248) should be < len (is 248)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 17

Group: 5

Verdict:

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

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

user output
3
3
2
2
2
...
view save

Error:
thread 'main' panicked at /build/rustc-kAv1jW/rustc-1.75.0+dfsg0ubuntu1~bpo0/library/alloc/src/vec/mod.rs:1458:13:
swap_remove index (is 249) should be < len (is 248)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 18

Group: 5

Verdict:

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

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

user output
3
3
3
3
3
view save

Error:
thread 'main' panicked at /build/rustc-kAv1jW/rustc-1.75.0+dfsg0ubuntu1~bpo0/library/alloc/src/vec/mod.rs:1458:13:
swap_remove index (is 248) should be < len (is 248)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 19

Group: 5

Verdict:

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

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

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

Error:
thread 'main' panicked at /build/rustc-kAv1jW/rustc-1.75.0+dfsg0ubuntu1~bpo0/library/alloc/src/vec/mod.rs:1458:13:
swap_remove index (is 248) should be < len (is 248)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 20

Group: 5

Verdict:

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

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

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

Error:
thread 'main' panicked at /build/rustc-kAv1jW/rustc-1.75.0+dfsg0ubuntu1~bpo0/library/alloc/src/vec/mod.rs:1458:13:
swap_remove index (is 248) should be < len (is 248)
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Test 21

Group: 5

Verdict:

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

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

user output
(empty)

Test 22

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

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

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

user output
0
1
1
0
0
...
view save

Test 23

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

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
1
1
1
1
1
...
view save

Test 24

Group: 5

Verdict: ACCEPTED

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

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

user output
1
1
1
1
1
...
view save

Test 25

Group: 5

Verdict: ACCEPTED

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

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

user output
1
1
1
1
1
...
view save

Test 26

Group: 5

Verdict: ACCEPTED

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

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

user output
2
2
2
2
2
...
view save

Test 27

Group: 5

Verdict: ACCEPTED

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

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

user output
0
0
0
0
0
...
view save

Tasks

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

Submissions (JuusoH)

2025-11-09 14:56:46 1002025-11-09 14:45:36 02025-11-09 14:40:44 02025-11-09 14:29:34 02025-11-09 14:18:51 02025-11-09 14:06:55 02025-11-08 16:15:27 602025-11-08 16:10:14 602025-11-08 16:05:00 602025-11-08 16:04:15 602025-11-08 15:57:08 602025-11-08 15:56:35 602025-11-08 15:55:51 602025-11-08 15:39:03 602025-11-08 15:10:12 602025-11-08 14:52:58 602025-11-08 14:51:23 02025-11-08 14:46:46 602025-11-08 14:39:03 602025-11-08 14:38:47 02025-11-08 14:25:33 602025-11-08 14:25:15 02025-11-08 13:36:22 2025-11-07 14:59:47 02025-11-07 14:55:09 02025-11-07 14:54:54 302025-11-07 14:30:03 602025-11-07 14:28:07 602025-11-07 13:52:47 02025-11-07 13:45:27 302025-11-07 13:42:26 302025-11-07 13:40:30 302025-11-07 13:40:03 02025-11-07 09:40:00 602025-11-07 09:38:22 602025-11-06 22:41:59 602025-11-06 22:41:23 302025-11-06 22:40:46 02025-11-06 22:33:59 602025-11-06 22:33:37 602025-11-06 22:30:09 302025-11-06 22:28:46 302025-11-06 22:27:10 02025-11-06 22:06:43 302025-11-06 21:47:21 02025-11-06 20:49:59 602025-11-06 20:44:17 602025-11-06 20:41:52 602025-11-06 19:07:48 02025-11-06 19:05:11 302025-11-06 19:02:57 302025-11-06 19:02:12 02025-11-06 18:55:26 602025-11-06 18:41:56 602025-11-06 18:33:58 02025-11-06 18:06:48 602025-11-06 17:53:47 602025-11-06 17:51:33 602025-11-06 17:49:44 602025-11-06 17:46:47 02025-11-06 17:46:06 602025-11-05 18:40:47 602025-11-04 20:09:56 602025-11-04 20:09:33 602025-11-04 20:07:28 602025-11-04 19:34:44 602025-11-04 19:15:00 602025-11-04 19:12:16 02025-11-04 19:11:50 02025-11-04 18:21:38 602025-11-04 18:13:20 602025-11-04 18:02:01 602025-11-04 18:01:21 602025-11-04 17:20:59 602025-11-04 15:31:18 302025-11-04 14:50:38 302025-11-04 14:46:49 302025-11-04 14:34:25 02025-11-04 14:29:06 02025-11-04 13:38:12 02025-11-03 15:47:07 302025-11-03 15:42:58 302025-11-03 15:36:33 302025-11-03 14:20:27 302025-10-31 10:36:22 302025-10-30 18:20:07 302025-10-30 17:46:20 302025-10-30 17:44:47 102025-10-30 17:10:46 0