Hypyt

use std::{io, usize, vec};

#[derive(Debug, Clone, PartialEq, Eq)]
struct Row {
    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 modifications = vec![false; n];
    let mut modification_targets: Vec<usize> = vec![0; n];

    for row in 0..n {
        if !modifications[row] {
            for rowi in 0..n {
                if map[row] == map[rowi] && row != rowi {
                    modifications[rowi] = true;
                    modification_targets[rowi] = row;
                }
            }
        }
    }

    let mut new_map: Vec<Vec<bool>> = Vec::new();
    for row in 0..n {
        if modifications[row] {
        } else {
            new_map.push(map[row].clone());
            modification_targets[row] = new_map.len() - 1;
        }
    }
    //dbg!(&modifications, &modification_targets);

    let n = new_map.len();
    let map = new_map;

    let mut rows: Vec<Row> = vec![
        Row {
            connections: Vec::new()
        };
        n
    ];

    for row in 0..n {
        let mut connections = vec![false; n];
        for column in 0..m {
            if map[row][column] {
                for rowi in 0..n {
                    if row != rowi && map[rowi][column] {
                        connections[rowi] = true;
                    }
                }
            }
        }
        //dbg!(&connections);
        for rowi in 0..n {
            if connections[rowi] {
                rows[row].connections.push(rowi);
            }
        }
    }
    //dbg!(&rows[198]);

    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();

            let mut y1 = iter.next().unwrap().parse::<usize>().unwrap() - 1;
            let x1 = iter.next().unwrap().parse::<usize>().unwrap() - 1;
            let mut y2 = iter.next().unwrap().parse::<usize>().unwrap() - 1;
            let x2 = iter.next().unwrap().parse::<usize>().unwrap() - 1;

            y1 = modification_targets[y1];
            y2 = modification_targets[y2];

            (y1, x1, y2, x2)
        };
        queries.push(((x1, y1), (x2, y2)));
    }

    let rows = rows;
    let queries = queries;

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

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.0.1 == query.1.1 {
        return 1;
    }

    let mut process_rows: Vec<usize> = Vec::new();
    let mut advantages = vec![false; rows];

    advantages[query.0.1] = true;

    for row in 0..rows {
        if map[row][query.0.0] {
            process_rows.push(row);
            used_rows[row] = true;
        }
    }
    if used_rows[query.1.1] {
        return 2;
    }

    loop {
        //dbg!(&process_rows);
        if used_rows[query.1.1] {
            return steps + 1;
        }

        let mut can_continue = false;
        let mut new_process_rows: Vec<usize> = Vec::new();
        let mut new_advantages = vec![false; rows];
        let mut can_still_use = vec![false; rows];

        let mut lowest_score = -1;

        for row in process_rows {
            for rowi in &map_rows[row].connections {
                if (!used_rows[*rowi]) || can_still_use[*rowi] {
                    used_rows[*rowi] = true;
                    new_process_rows.push(*rowi);
                    can_continue = true;
                    if advantages[row] {
                        new_advantages[*rowi] = true;
                    }

                    if *rowi == query.1.1 {
                        if advantages[row] {
                            if lowest_score != -1 {
                                if map[row][query.1.0] {
                                    lowest_score = i32::min(lowest_score, steps + 1);
                                } else {
                                    lowest_score = i32::min(lowest_score, steps + 2);
                                    can_still_use[*rowi] = true;
                                }
                            } else {
                                // Sometimes goes to wrong branch??????
                                if map[row][query.1.0] {
                                    lowest_score = steps + 1;
                                } else {
                                    lowest_score = steps + 2;
                                    can_still_use[*rowi] = true;
                                }
                            }
                        } else {
                            //dbg!(row, rowi);
                            if lowest_score != -1 {
                                if map[row][query.1.0] {
                                    lowest_score = i32::min(lowest_score, steps + 2);
                                } else {
                                    lowest_score = i32::min(lowest_score, steps + 3);
                                }
                            } else {
                                // Sometimes goes to wrong branch??????
                                if map[row][query.1.0] {
                                    lowest_score = steps + 2;
                                } else {
                                    lowest_score = steps + 3; // 9946 branch
                                }
                            }
                            can_still_use[*rowi] = true;
                        }
                    }
                }
            }
        }

        if lowest_score != -1 {
            return lowest_score;
        }

        if !can_continue {
            return -1;
        }

        process_rows = new_process_rows;
        advantages = new_advantages;

        steps += 2;
    }
}

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: RUNTIME ERROR

thread 'main' panicked at input/code.rs:134:17:
index out of bounds: the len is 125 but the index is 210
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

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

Test 25

Group: 5

Verdict: ACCEPTED

Test 26

Group: 5

Verdict: WRONG ANSWER

Test 27

Group: 5

Verdict: ACCEPTED