Hypyt

use std::{io, vec};

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

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 {
                if map[row][column] {
                    cell.vertical_connections.push(row);
                }
            }
            for column in 0..m {
                if map[row][column] {
                    cell.horizontal_connections.push(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 used_columns = vec![false; columns];
    let mut used_rows = vec![false; rows];

    used_columns[query.0.0] = true;
    used_rows[query.0.1] = true;

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

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

    loop {
        steps += 1;
        if used_rows[query.1.1] || used_columns[query.1.0] {
            return steps;
        }

        let mut new_process_points = Vec::new();

        let mut can_continue = false;

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

        if !can_continue {
            return -1;
        }

        process_points = new_process_points;
    }
}

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: ACCEPTED

Test 11

Group: 3, 4, 5

Verdict: ACCEPTED

Test 12

Group: 4, 5

Verdict: ACCEPTED

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