#![warn(clippy::pedantic)]

use std::io::stdin;

use petgraph::{
    algo::k_shortest_path,
    graph::{Graph, NodeIndex},
    visit::IntoNodeReferences,
};

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum NodeKind {
    Start,
    End,
}

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
struct NodeData {
    kind: Option<NodeKind>,
    height: u32,
}

fn main() {
    // graph of "downhill" edges - edge from A to B means that A is reachable from B
    let mut graph = Graph::<NodeData, (), _>::new();

    let grid: Vec<Vec<NodeIndex>> = stdin()
        .lines()
        .map(|line| {
            line.unwrap()
                .chars()
                .map(|c| {
                    let (kind, c) = match c {
                        'S' => (Some(NodeKind::Start), 'a'),
                        'E' => (Some(NodeKind::End), 'z'),
                        c => (None, c),
                    };

                    let height = u32::from(c) - u32::from('a');
                    let data = NodeData { kind, height };
                    graph.add_node(data)
                })
                .collect()
        })
        .collect();

    for (x, row) in grid.iter().enumerate() {
        for (y, &node_id) in row.iter().enumerate() {
            let node = graph[node_id];

            let x = i32::try_from(x).unwrap();
            let y = i32::try_from(y).unwrap();
            let neighbours =
                [(-1, 0), (0, -1), (1, 0), (0, 1)]
                    .into_iter()
                    .filter_map(|(dx, dy)| {
                        let x = usize::try_from(x + dx).ok()?;
                        let y = usize::try_from(y + dy).ok()?;
                        grid.get(x)?.get(y)
                    });

            for &neighbour_id in neighbours {
                let neighbour = graph[neighbour_id];
                if node.height <= (neighbour.height + 1) {
                    // `node` is reachable from `neighbour`
                    graph.add_edge(node_id, neighbour_id, ());
                }
            }
        }
    }

    let end = graph
        .node_references()
        .find_map(|(id, node)| (node.kind == Some(NodeKind::End)).then_some(id))
        .unwrap();
    let paths = k_shortest_path(&graph, end, None, 1, |_| 1);

    let start = graph
        .node_references()
        .find_map(|(id, node)| (node.kind == Some(NodeKind::Start)).then_some(id))
        .unwrap();
    println!("{:?}", paths[&start]);

    println!(
        "{:?}",
        paths
            .into_iter()
            .filter_map(|(start_id, steps)| (graph[start_id].height == 0).then_some(steps))
            .min()
            .unwrap()
    );
}
