Hypyt

warning: unused import: `collections::HashSet`
 --> input/code.rs:1:11
  |
1 | use std::{collections::HashSet, io, vec};
  |           ^^^^^^^^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: 1 warning emitted

use std::{collections::HashSet, io, vec};

#[derive(Debug)]
struct Cell {
    vertical_connections: Vec<bool>,
    horizontal_connections: Vec<bool>,
}

fn main() {
    let mut input = String::new();
    io::stdin().read_line(&mut input).unwrap();
    let (n, m, q): (usize, usize, usize) = {
        let mut iter = input.split_whitespace();
        (
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
            iter.next().unwrap().parse().unwrap(),
        )
    };
    let mut map: Vec<Vec<bool>> = Vec::new();
    for _ in 0..n {
        let mut input = String::new();
        io::stdin().read_line(&mut input).unwrap();
        map.push(input.trim().chars().map(|x| x == '.').collect());
    }
    let mut cells: Vec<Vec<Option<Cell>>> = Vec::new();
    for row in 0..n {
        let mut cell_line = Vec::new();
        for column in 0..m {
            if !map[row][column] {
                cell_line.push(None);
                continue;
            }
            let mut cell = Cell {
                vertical_connections: Vec::new(),
                horizontal_connections: Vec::new(),
            };

            for row in 0..n {
                cell.vertical_connections.push(map[row][column]);
            }
            for column in 0..m {
                cell.horizontal_connections.push(map[row][column]);
            }
            cell_line.push(Some(cell));
        }
        cells.push(cell_line);
    }

    let mut queries: Vec<((usize, usize), (usize, usize))> = Vec::new();
    for _ in 0..q {
        let mut input = String::new();
        io::stdin().read_line(&mut input).unwrap();
        let (y1, x1, y2, x2): (usize, usize, usize, usize) = {
            let mut iter = input.split_whitespace();
            (
                iter.next().unwrap().parse().unwrap(),
                iter.next().unwrap().parse().unwrap(),
                iter.next().unwrap().parse().unwrap(),
                iter.next().unwrap().parse().unwrap(),
            )
        };
        queries.push(((x1 - 1, y1 - 1), (x2 - 1, y2 - 1)));
    }

    let map = cells;
    let queries = queries;

    for query in queries {
        println!("{}", process_query(&map, query));
    }
}

// NOTE: Needs to be O(n+m)
fn process_query(cells: &Vec<Vec<Option<Cell>>>, query: ((usize, usize), (usize, usize))) -> i32 {
    let mut steps = 0;
    let columns = cells[0].len();
    let rows = cells.len();
    let mut columns_left: Vec<usize> = Vec::with_capacity(columns);
    let mut rows_left: Vec<usize> = Vec::with_capacity(rows);

    for i in 0..columns {
        if i != query.0.0 {
            columns_left.push(i);
        }
    }
    for i in 0..rows {
        if i != query.0.1 {
            rows_left.push(i);
        }
    }

    let mut process_points = vec![query.0];

    if query.0 == query.1 {
        return 0;
    }

    loop {
        steps += 1;
        if !rows_left.contains(&query.1.1) || !columns_left.contains(&query.1.0) {
            return steps;
        }

        let mut new_process_points = Vec::new();

        let mut used_columns = vec![false; columns];
        let mut used_rows = vec![false; columns];

        let mut can_continue = false;

        for point in process_points {
            for row in &rows_left {
                if cells[point.1][point.0]
                    .as_ref()
                    .unwrap()
                    .vertical_connections[*row]
                    && !used_rows[*row]
                {
                    new_process_points.push((point.0, *row));
                    used_rows[*row] = true;
                    can_continue = true;
                }
            }
            for column in &columns_left {
                if cells[point.1][point.0]
                    .as_ref()
                    .unwrap()
                    .horizontal_connections[*column]
                    && !used_columns[*column]
                {
                    new_process_points.push((*column, point.1));
                    used_columns[*column] = true;
                    can_continue = true;
                }
            }
        }

        if !can_continue {
            return -1;
        }

        let mut new_columns_left: Vec<usize> = Vec::with_capacity(columns_left.len());
        let mut new_rows_left: Vec<usize> = Vec::with_capacity(rows_left.len());

        for column in &columns_left {
            if !used_columns[*column] {
                new_columns_left.push(*column);
            }
        }
        for row in &rows_left {
            if !used_rows[*row] {
                new_rows_left.push(*row);
            }
        }

        process_points = new_process_points;
        columns_left = new_columns_left;
        rows_left = new_rows_left;
    }
}

Test 1 (public)

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 2

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 3

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 4

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 5

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 6

Group: 2, 5

Verdict: ACCEPTED

Test 7

Group: 2, 5

Verdict: ACCEPTED

Test 8

Group: 2, 5

Verdict: ACCEPTED

Test 9

Group: 3, 4, 5

Verdict: ACCEPTED

Test 10

Group: 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 3, 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 4, 5

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 18

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 19

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 20

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 21

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 23

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 24

Group: 5

Verdict: ACCEPTED

Test 25

Group: 5

Verdict: ACCEPTED

Test 26

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 27

Group: 5

Verdict: ACCEPTED