Hypyt

use std::{io, vec};

#[derive(Debug, Clone)]
struct Row {
    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 rows: Vec<Row> = vec![
        Row {
            connections: vec![false; n]
        };
        n
    ];
    for row in 0..n {
        for column in 0..m {
            if map[row][column] {
                for rowi in 0..n {
                    if map[rowi][column] {
                        rows[row].connections[rowi] = true;
                    }
                }
            }
        }
    }

    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 rows = rows;
    let queries = queries;

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

// NOTE: Needs to be O(n+m)
fn process_query(
    map_rows: &Vec<Row>,
    map: &Vec<Vec<bool>>,
    query: ((usize, usize), (usize, usize)),
) -> i32 {
    let mut steps = 1;
    let rows = map_rows.len();
    let mut used_rows = vec![false; rows];

    if query.0 == query.1 {
        return 0;
    } else if query.0.0 == query.1.0 || query.1.0 == query.1.1 {
        return 1;
    }

    let mut process_rows = vec![false; rows];

    process_rows[query.0.1] = true;
    for row in 0..rows {
        if map[row][query.0.0] {
            process_rows[row] = true;
        }
    }
    for row in 0..rows {
        if process_rows[row] {
            used_rows[row] = true;
        }
    }

    let mut can_continue = false;

    loop {
        if used_rows[query.1.1] {
            return steps;
        }

        for row in 0..rows {
            if process_rows[row] {
                process_rows[row] = false;
                for row in 0..rows {
                    if map_rows[row].connections[row] {
                        if !used_rows[row] {
                            used_rows[row] = true;
                            process_rows[row] = true;
                            can_continue = true
                        }
                    }
                }
            }
        }

        if !can_continue {
            return -1;
        }

        steps += 2;
    }
}

Test 1 (public)

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 2

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 3

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 4

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 5

Group: 1, 2, 3, 4, 5

Verdict: WRONG ANSWER

Test 6

Group: 2, 5

Verdict: WRONG ANSWER

Test 7

Group: 2, 5

Verdict: WRONG ANSWER

Test 8

Group: 2, 5

Verdict: WRONG ANSWER

Test 9

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 10

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 11

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 12

Group: 4, 5

Verdict: WRONG ANSWER

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: WRONG ANSWER

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: WRONG ANSWER

Test 27

Group: 5

Verdict: ACCEPTED