use grid::Grid;

const  ADJACENTS: [(i16, i16); 4] = [
    (0, -1),
    (1, 0),
    (0, 1),
    (-1, 0),
];

const PICOSECONDS: i16 = 100;

fn main() {
    let time = std::time::Instant::now();

    let input: Vec<_> = include_str!("../input.txt").lines().collect();
    let mut grid: Grid<char> = Grid::new(input.len(), input[0].len());
    let mut end: Option<(i16, i16)> = None;

    for (y, row) in input.into_iter().enumerate() {
        for (x, c) in row.chars().enumerate() {
            grid[(y, x)] = c;

            if c == 'E' {
                end = Some((x as i16, y as i16));
            }
        }
    }

    let mut distances: Grid<Option<i16>> = Grid::new(grid.rows(), grid.cols());
    distances.fill(None);

    let mut next = Some(end.unwrap().clone());
    let mut distance = 0;
    let mut cheats = 0;

    loop {
        if next.is_none() {
            break;
        }

        let (cx, cy) = next.unwrap();
        next = None;

        distances[(cy as usize, cx as usize)] = Some(distance);

        for (xd, yd) in ADJACENTS {
            let x = cx + xd;
            let y = cy + yd;

            if let Some(cell) = grid.get(y, x) {
                match cell {
                    '#' => if distance >= PICOSECONDS {
                        let tx = x + xd;
                        let ty = y + yd;
                        if let Some(&Some(dist)) = distances.get(ty, tx) {
                            if distance - dist - 2 >= PICOSECONDS {
                                cheats += 1;
                            }
                        }
                    },
                    '.' | 'S' => {
                        grid[(y as usize, x as usize)] = 'O';
                        next = Some((x, y));
                    },
                    'O' | 'E' => (),
                    _ => unimplemented!()
                }
            }
        }

        distance += 1;
    }

    println!("Time elapsed: {:?}", time.elapsed());
    println!("Cheats: {}", cheats);

    // // For debugging Grid<char>:
    // let grid_out = grid.iter_rows()
    //     .map(|row| row.into_iter().collect::<String>())
    //     .collect::<Vec<String>>()
    //     .join("\n");
    // println!("Grid:\n{}", grid_out);
}