Hypyt

use std::io::{self};

const X: usize = 0;
const Y: usize = 1;

fn main() {
    let input = io::stdin();
    let mut input_buf: String = "".to_string();
    let _ = input.read_line(&mut input_buf);
    let line1: Vec<&str> = input_buf.split_whitespace().collect();
    // let start_time = Instant::now();
    let height: u8 = line1[0].parse().unwrap();
    let width: u8 = line1[1].parse().unwrap();
    let query_count: u32 = line1[2].parse().unwrap();
    let mut x_connections: Vec<Vec<u8>> = Vec::with_capacity(height as usize);
    let mut y_connections: Vec<Vec<u8>> = Vec::with_capacity(width as usize);
    y_connections.append(&mut vec![vec![]; width as usize]);
    input_buf = "".to_string();
    for y in 0..height {
        let _ = input.read_line(&mut input_buf);
        x_connections.push(vec![]);
        for x in 0..input_buf.as_bytes().len() {
            if input_buf.as_bytes()[x] == '.' as u8 {
                x_connections[y as usize].push(x as u8);
                y_connections[x].push(y);
            }
        }
        // eprintln!("{y}");
        input_buf = "".to_string();
    }
    // eprintln!("x_connections.len() = {}", x_connections.len());
    // eprintln!("y_connections.len() = {}", y_connections.len());
    // for line in y_connections.iter() {
    //     for node in line.iter() {
    //         eprintln!("\t {node}");
    //     }
    //     eprintln!("")
    // }
    // for line in x_connections.iter() {
    //     for node in line.iter() {
    //         eprintln!("\t {node}");
    //     }
    //     eprintln!("")
    // }
    for _i in 0..query_count {
        let _ = input.read_line(&mut input_buf);
        let line: Vec<&str> = input_buf.split_whitespace().collect();
        println!(
            "{}",
            pathfind(
                &x_connections,
                &y_connections,
                [line[1].parse().unwrap(), line[0].parse().unwrap()],
                [line[3].parse().unwrap(), line[2].parse().unwrap()]
            )
        );
        input_buf = "".to_string();
    }
}

#[derive(Clone)]
struct Node {
    x: u8,
    y: u8,
    f: u16,
    g: u16,
    // parent: usize,
}

fn pathfind(
    x_connections: &Vec<Vec<u8>>,
    y_connections: &Vec<Vec<u8>>,
    mut start: [u8; 2],
    mut target: [u8; 2],
) -> i16 {
    start[0] -= 1;
    start[1] -= 1;
    target[0] -= 1;
    target[1] -= 1;
    // eprintln!("Target: {}, {}", target[X], target[Y]);
    // eprintln!("start: {}, {}", start[X], start[Y]);
    if x_connections[start[Y] as usize].len() == 0 && y_connections[start[X] as usize].len() == 0 {
        return -1;
    }
    if x_connections[target[Y] as usize].len() == 0 && y_connections[target[X] as usize].len() == 0
    {
        return -1;
    }
    if target[X] == start[X] && target[Y] == start[Y] {
        return 0;
    }
    let mut valid_node = false; //if the node is not present in its own connections it's invalid
    for node in x_connections[target[Y] as usize].iter() {
        if node == &target[X] {
            // eprintln!("\tFound:{node}");
            valid_node = true;
            break;
        }
    }
    if !valid_node {
        return -1;
    }
    for node in y_connections[target[X] as usize].iter() {
        if node == &target[Y] {
            // eprintln!("Found:{node}");
            valid_node = true;
            break;
        }
    }
    if !valid_node {
        return -1;
    }
    valid_node = false;
    for node in x_connections[start[Y] as usize].iter() {
        if node == &start[X] {
            // eprintln!("Found:{node}");
            valid_node = true;
            break;
        }
    }
    if !valid_node {
        return -1;
    }
    for node in y_connections[start[X] as usize].iter() {
        if node == &start[Y] {
            // eprintln!("Found:{node}");
            valid_node = true;
            break;
        }
    }
    if !valid_node {
        return -1;
    }
    if start[Y] == target[Y] {
        return 1;
    }
    if start[X] == target[X] {
        return 1;
    }
    let mut open: Vec<Node> = vec![Node {
        x: start[X],
        y: start[Y],
        f: 0,
        g: 0,
        // parent: 0,
    }];
    let mut closed: Vec<Node> = vec![];
    while open.len() > 0 {
        let mut smallest_f = open[0].f;
        let mut q = 0;
        for node in 0..open.len() {
            //smallest f
            if open[node].f < smallest_f {
                q = node;
                smallest_f = open[node].f;
            }
        }
        // eprintln!("\t{q}");
        // eprintln!("\t{},{},{},{}", open[q].x, open[q].y, open[q].f, open[q].g,);
        closed.push(open.remove(q));
        q = closed.len() - 1; //new index of q
        let mut successors: Vec<Node> = vec![];
        let parent = &closed[q];
        for x in x_connections[parent.y as usize].iter() {
            successors.push(Node {
                x: *x,
                y: parent.y,
                f: 0,
                g: 0,
                // parent: q,
            });
        }
        for y in y_connections[parent.x as usize].iter() {
            successors.push(Node {
                x: parent.x,
                y: *y,
                f: 0,
                g: 0,
                // parent: q,
            });
        } //adds the suucessors of q to open
        for succesor in successors.iter_mut() {
            if succesor.x == target[X] as u8 || succesor.y == target[Y] as u8 {
                return (parent.g + 2) as i16;
            } else {
                succesor.g = parent.g + 1;
                succesor.f = (target[X] as i16 - succesor.x as i16 + target[Y] as i16
                    - succesor.y as i16)
                    .abs() as u16
                    + succesor.g;
            }
            let mut duplicate = false;
            //check if succesor is a duplicate
            for node in 0..open.len() {
                if succesor.x == open[node].x
                    && succesor.y == open[node].y
                    && succesor.f >= open[node].f
                {
                    duplicate = true;
                    break;
                }
            }
            if duplicate {
                continue;
            }
            for node in 0..closed.len() {
                if succesor.x == closed[node].x
                    && succesor.y == closed[node].y
                    && succesor.f >= closed[node].f
                {
                    duplicate = true;
                    break;
                }
            }
            if duplicate {
                continue;
            }
            open.push(succesor.clone());
        }
    }
    return -1;
}
/*
test:
16 24 10
.*.**.*.****.*.**.*.****
*...**...****...**...***
**********..**********..
*..*.*..*.***..*.*..*.**
.*.**.*.****.*.**.*.****
*...**...****...**...***
**********..**********..
*..*.*..*.***..*.*..*.**
.*.**.*.****.*.**.*.****
*...**...****...**...***
**********..**********..
*..*.*..*.***..*.*..*.**
.*.**.*.****.*.**.*.****
*...**...****...**...***
**********..**********..
*..*.*..*.***..*.*..*.**
1 1 1 3
2 2 2 2
1 1 4 5
4 5 2 4
3 6 2 2
3 11 7 8
3 11 13 7
3 3 8 15
12 15 6 12
10 8 5 1

 */

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

Test 5

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 6

Group: 2, 5

Verdict: ACCEPTED

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