use pathfinding::directed::yen::yen;

#[test]
fn issue507() {
    let grid: &Vec<Vec<char>> = &INPUT.lines().map(|l| l.chars().collect()).collect();
    let start = (1_usize, 0_usize);
    let end = (grid[0].len() - 2, grid.len() - 1);
    let k = 10;
    let k_shortest_paths = yen(
        &start,
        |&(x, y)| {
            let dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)];
            dirs.into_iter().filter_map(move |(dx, dy)| {
                let (nx, ny) = (x.wrapping_add_signed(dx), y.wrapping_add_signed(dy));
                let tile = *grid.get(ny)?.get(nx)?;
                match tile {
                    'v' if dy == -1 => None,
                    '>' if dx == -1 => None,
                    '#' => None,
                    _ => Some(((nx, ny), 1)),
                }
            })
        },
        |&pos| pos == end,
        k,
    );
    let path_lengths: Vec<_> = k_shortest_paths.iter().map(|(_, l)| l).collect();
    for (a, b) in path_lengths.iter().zip(path_lengths.iter().skip(1)) {
        assert!(a <= b);
    }
}

const INPUT: &str = "#.###########################################################################################################################
#.#.....#...###.......#.....#.......#.......###...#...#.......###...###...#####...#...###...###...#.....#.....#...#...###...#
#.#.###.#.#.###.#####.#.###.#.#####.#.#####.###.#.#.#.#.###.#.###.#.###.#.#####.#.#.#.###.#.###.#.#.###.#.###.#.#.#.#.###.#.#
#.#...#...#...#.....#.#...#.#.#.....#.#.....#...#.#.#.#.#...#...#.#...#.#.....#.#.#.#.#...#...#.#.#...#.#...#...#...#.#...#.#
#.#.#.....#.#...###.#...#.#.#.#...>.>.#...#.#...#.....#.#...#...#...#.#.#...#.....#.....#.#...#...#...#.#.#.#.....#.#.#...#.#
#.#.#.#####.###.###.###.#.#.#.#####v#######.#.#.#.#####.#.#.#.#.###.#.#.#####.#####.#####.#.###.###.#.#.#.#.#.###.#.#.#####.#
#.#.#.#.#.###.#v#.#####.#.#.#.#.#####.#######.#.#####.#.#.#####.#.#######.#####.#.#####.#.###.#.###.#.#.#.#.###.#####.#.#####
#.#####.###.#################.#########.#######.#######.#.#.#.###########.#.#.#############.#.#.###.#.#####.#.#.###########.#
#.....#.....#...###.........#.......#...#.......#####...#.....#####.....#...#...#.....#.....#...#...#.....#.#...#.........#.#
#####.#######.#.###.#######.#######.#.###.###########.#############.###.#######.#.###.#.#########.#######.#.#####.#######.#.#
#.....#.......#.....#.......#.......#.###.........#...#...#.........#...#.......#...#.#...###.....#...###...#...#.......#.#.#
#.#####.#############.#######.#######.###########.#.###.#.###########.###.#########.#.###.###.#####.#.#######.#.#######.#.#.#
#.......#.......#.....###...#.........#...........#...#.#...........#...#...........#...#.#...#...#.#.###...#.#.#...#...#.#.#
#########.#####.#.#######.#.###########.#############.#.###.#######.###.###############.#.#.###.#.#.#.###.#.#.#.#.#.#v###.#.#
#...#...#.....#...#...###.#.###...###...#...........#...#.........#.....###...#...#...#...#...#.#.#.#.#...#...#...#.>.###.#.#
#.#.#.#.#####.#####.#.###.#.###.#.###.###.#########.#####v#######.#########.#.#.#.#.#.#######.#.#.#.#.#.#############v###.#.#
#.#...#.......#...#.#.#...#.#...#...#.....#.........#...>.>.......#...###...#.#.#...#...#...#.#.#.#.#.#.#...#.....#...###.#.#
#.#############.#.#.#.#.###.#.#####.#######.#########.###v#########.#.###.###.#.#######.#.#.#.#.#.#.#.#.#.#.#.###.#.#####.#.#
#.#.............#...#.#...#.#...#...###.....###...#...#...#.......#.#...#...#.#.....#...#.#.#.#.#.#.#...#.#...###...#...#...#
#.#.#################.###.#.###.#.#####.#######.#.#.###.#########.#.###.###.#.#####.#.###.#.#v#.#.#.#####.###########.#.#####
#...#...###...........#...#...#.#.....#.....###.#.#.#...#.........#...#...#.#.#...#.#.#...#.>.>.#.#.....#.............#.....#
#####.#.###v###########.#####.#.#####.#####.###.#.#.#.###.###########.###.#.#.#.#.#.#.#.#####v###.#####.###################.#
#.....#...#.>...###...#.....#.#.#.....#...#.#...#...#...#.#...###...#...#.#.#.#.#.#.#...#...#.###...#...#...........#.......#
#.#######.#v###.###.#.#####.#.#.#.#####.#.#v#.#########.#.###.###.#.###.#.#.#.#.#.#.#####.#.#.#####.#.###.#########.#.#######
#.#.....#.#...#.#...#.#...#.#.#.#.#...#.#.>.>.#.....#...#.#.#.#...#.....#.#.#.#.#.#.#.....#...#...#...#...#.......#...#...###
#.#.###.#.###.#.#.###.#.#.#.#.#.#.#.#.#.###v###.###.#.###.#.#.#.#########.#.#.#.#.#.#.#########.#.#####.###.#####.#####.#.###
#...###.#.....#...#...#.#.#.#.#.#.#.#...###.###.#...#...#.#.#.#...###...#...#...#...#...........#...###.....#.....#...#.#...#
#.#...#...#.#.#...#.#.#.#...#.#.#.#.#.....#...#...#.....#.#...###...#.....#...#.###...###...#.....#.#.#.#.#...........#.....#
#.#.#.#####.#.#.#.#.#.#.###.#.#.#.#.#.#####.#.#########.#.#.#.#################.#############.#####.#.#.#.#################.#
#...#.....#...#.#.#.#.#.#...#.#.#.#.#...#...#.......###...#.#.#.........#...#...#.....#.....#...#...#.#.#.###...#...#.......#
#########.#####.#.#.#.#.#.###.#.#.#.###.#.#########.#######.#.#.#######.#.#.#.###.###.#.###.###.#.###.#.#.###v#.#.#.#.#######
#.........#...#.#.#.#.#.#.###.#.#.#.###.#...#.......#...#...#.#.......#...#.#.###...#.#...#.#...#...#.#.#.#.>.#...#...#...###
#.#########.#.#.#.#.#.#.#.###.#.#.#.###v###.#.#######.#.#.###.#######.#####.#.#####.#.###.#.#.#####.#.#.#.#.#v#########.#.###
#.#.....#...#...#...#.#.#.#...#.#.#...>.>...#.......#.#.#.....#...#...#...#...#...#.#.....#...#...#.#.#.#...#...........#...#
#.#.###v#.###########.#.#.#.###.#.#####v###########.#.#.#######.#.#.###.#.#####.#.#.###########.#.#.#.#.###################.#
#.#.###.>.#...#...###...#.#.#...#.#.....###.....#...#.#.#.....#.#.#.....#.......#.#.........#...#...#.#.#...........#.......#
#.#.###v###.#.#.#.#######.#.#.###.#.#######.###.#.###.#.#.###.#.#.###############.#########.#.#######.#.#.#########.#.#######
#...#...#...#.#.#.......#...#.....#.#.....#...#...###.#.#.....#.#.###.............#...#.....#.......#.#.#.........#.#.....###
#####.###.###.#.#######.###########.#.###.###.#######.#.###.###.#.###v#############.#.#.###########.#.#.#########.#.#####.###
#...#.....###.#.#.......#.........#...#...###...#...#.#.#.....#.#...>.>.###...#...#.#.#...#...#...#.#...###.......#.....#...#
#.#.#########.#.#.#######.#######.#####.#######.#.#.#.#.#.###.#.#####v#.###.#.#.#.#.#.###v#.#.#.#.#.#######.###########.###.#
#.#...........#.#...###...#...#...#.....#...###.#.#.#.#.#.###.#.#.....#.....#.#.#...#.#.>.>.#...#.#...#.....#...#...###...#.#
#.#############.###.###.###.#.#.###.#####.#.###.#.#.#.#.#.###.#.#.###########.#.#####.#.#v#######.###.#.#####.#.#.#.#####.#.#
#.#...#.....#...###.....#...#...###.......#...#.#.#.#.#...#...#.#.........#...#...#...#.#.#...###.....#.......#...#.....#.#.#
#.#.#.#.###.#.###########.###################.#.#.#.#.#####.###.#########.#.#####.#.###.#.#.#.#########################.#.#.#
#...#.#.#...#.#.........#.###...#.............#.#.#.#...#.......#.......#.#...#...#...#.#.#.#...###.....#...............#.#.#
#####.#.#.###.#.#######.#.###.#.#.#############.#.#.###.#.#######.#####.#.###.#.#####.#.#.#.###.###.###.#.###############.#.#
#.....#.#.....#.......#.#...#.#.#.............#...#.....#..####...#...#...###.#.#...#...#...###.....#...#...............#...#
#.#####.#############.#.###.#.#.#############.#################.###.#.#######.#.#.#.#################.#################.#####
#.......###...#...#...#.....#.#.....#.........#...###......##...#...#...#...#...#.#...#.....#.......#.#...#.......#...#.....#
###########.#.#.#.#.#########.#####.#.#########.#.###.#######.###.#####.#.#.#####.###.#.###.#.#####.#.#.#.#.#####.#.#.#####.#
#...........#.#.#...#.....#...#.....#...........#...#.......#...#.....#.#.#.#...#.#...#...#.#.....#...#.#.#.....#.#.#...#...#
#.###########.#.#####.###.#.###.###################.#######.###.#####.#.#.#.#.#.#.#.#####.#.#####v#####.#.#####v#.#.###.#.###
#...........#.#.......#...#...#.###...#.......#.....#.......#...#.....#...#.#.#...#.#.....#.....>.>.#...#.#...>.#.#...#...###
###########.#.#########.#####.#.###.#.#v#####.#.#####.#######v###.#########.#.#####.#.###########v#.#.###.#.###v#.###.#######
#...........#...........#.....#...#.#.>.>.###.#.#...#.......>.>.#.....#.....#.....#...#...###...#.#.#...#...#...#...#.......#
#.#######################.#######.#.###v#.###.#.#.#.#########v#.#####.#.#########.#####.#.###.#.#.#.###.#####.#####.#######.#
#...........#.......#...#.......#.#.#...#...#...#.#.#...###...#.#...#.#.#...#...#.#.....#.....#...#...#.#.....#####.#.......#
###########.#.#####.#.#.#######.#.#.#.#####.#####.#.#.#.#######.#.#.#.#.#.#.#.#.#.#.#################.#.#.#########.#.#######
#...###...#.#.#.....#.#.#.....#.#.#.#.#...#...#...#.#.#.#.>...#...#...#...#.#.#...#.................#...#.......###...#...###
#.#.###.#.#.#.#.#####.#.#.###.#.#.#.#.#.#.###.#.###.#.#.#.###.#############.#.#####################.###########.#######.#.###
#.#.....#.#...#.#...#.#...###.#.#.#.#.#.#...#...#...#.#.#.#...#...###...###...###...#...............#.....#...#.....#...#...#
#.#######.#####.#.#.#.#######.#.#.#.#.#.###.#####.###.#.#.#####.#.###.#.#########.#.#.###############.###.#.#.#####.#.#####.#
#.......#.....#.#.#.#.......#...#.#.#.#.###.....#...#.#.#.#.###.#.#...#...###.....#.#...............#...#...#.......#.#.....#
#######.#####.#.#.#v#######.#####.#.#.#.#######.###.#.#.#.#.###.#.#.#####.###.#####.###############.###.#############.#.#####
#.......#.....#.#.#.>.....#.....#...#...###.....###.#.#...#.#...#...#...#...#.....#.............#...###...............#.....#
#.#######.#####.#.#v#####.#####.###########.#######.#.#######.#######.#.###.#####.#############.#.#########################.#
#.......#.#...#...#.....#.#...#...#.........###.....#.....#...#...#...#.....#.....#...#.....###...#.........................#
#######.#.#.#.#########.#.#.#.###.#.###########.#########.#####.#.#.#########.#####.#.#.###.#######.#########################
#.......#...#.###...#...#.#.#.#...#...........#.#...#...#.#...#.#.#.........#.#.....#...###.....###...............#.........#
#.###########.###.#.#.###.#.#.#.#############.#.#.#.#.#.#.###.#.#.#########.#.#.###############.#################.#.#######.#
#.#.........#...#.#...###...#...#...#.........#...#.#.#...#.#...#...........#...#.............#.....#.............#.#.......#
#.#.#######.###.#.###############.#.#.#############.#.#####.#####################.###########.#####.#.#############.#.#######
#.#.#.......###.#.#.....#...#...#.#.#...#.....#...#.#.#...#.................#...#...........#.#.....#.#.....#...#...#.......#
#.#.#.#########.#.#.###.#.#.#.#.#.#.###.#.###.#.#.#.#.#.#.#################.#.#.###########.#.#.#####.#.###.#.#.#.#########.#
#.#.#.......###.#.#.#...#.#.#.#.#.#.###...#...#.#.#...#.#.#.......#.........#.#.....#.......#...#...#...###...#...#.....#...#
#.#.#######.###.#.#.#.###.#.#.#.#.#.#######.###.#.#####.#.#######.#.#########.#####.#.###########.#.###############.###.#.###
#.#.#.......#...#.#.#.#...#.#.#.#.#.#.....#.....#...###.#.#.#...#...#...#...#.#.....#.......#...#.#.###.......#...#...#.#...#
#.#.#.#######.###.#.#.#.###.#.#.#.#.#.###.#########.###.#.#.#.#.#####.#.#.#.#.#.###########.#.#.#.#.###.#####.#.#.###.#.###.#
#.#.#.....###.....#.#.#...#.#.#.#.#.#.#...#.........#...#.#...#.....#.#.#.#.#.#.#...###...#.#.#.#.#.#...#...#...#.#...#.....#
#.#.#####.#########.#.###.#.#.#.#.#.#.#.###v#########.###.#########.#.#.#.#.#.#.#.#.###.#.#v#.#.#.#.#.###.#.#####.#.#########
#...#####...#...###.#.#...#.#.#.#.#.#.#...>.>...#...#.#...#.........#.#.#.#.#.#...#...#.#.>.>.#...#.#.....#.....#...###...###
###########.#.#.###.#.#.###.#.#.#.#.#.#####v###.#.#.#.#.###.#########.#.#.#.#.#######.#.###v#######.###########.#######.#.###
#...###.....#.#.#...#.#.###.#.#...#...###...#...#.#.#.#...#...#.....#.#.#.#...###...#...#...#.......#...........###...#.#.###
#.#.###v#####.#.#.###.#.###.#.###########.###.###.#.#.###.###.#.###.#.#.#.#######.#.#####.###.#######.#############.#.#.#.###
#.#.###.>.....#.#...#.#.#...#...#.........###...#.#.#...#.....#...#.#.#.#.....#...#...#...#...###...#.......#.....#.#.#.#.###
#.#.###v#######.###.#.#.#.#####.#.#############.#.#.###.###v#####.#.#.#.#####.#.#####.#.###.#####.#.#######v#.###.#.#.#.#.###
#.#.###.......#.....#.#.#.#.....#...........#...#.#.....###.>.#...#...#.....#.#.....#.#...#.#...#.#...#...>.#.#...#.#...#...#
#.#.#########.#######.#.#.#.###############.#.###.#########v#.#.###########.#.#####.#.###.#.#.#.#.###.#.###v#.#.###.#######.#
#.#...........###...#.#.#...#...###...#.....#...#.#.........#.#.#.........#.#...#...#...#.#...#.#...#.#.#...#.#.....#.....#.#
#.###############.#.#.#.#####.#.###.#.#.#######.#.#.#######.#.#.#.#######.#.###.#.#####.#.#####.###.#.#.#.###.#######.###.#.#
#.................#.#.#...#...#.#...#...#.....#...#.........#...#.......#.#.....#.....#.#.#...#.#...#.#.#...#.###...#...#.#.#
###################.#.###.#.###.#.#######.###.#############.###########.#.###########.#.#.#.#.#.#.###.#.###.#.###.#.###.#.#.#
#...................#.....#...#.#.........#...###...#.......#...###.....#...###...#...#...#.#.#.#.#...#.#...#.#...#.....#.#.#
#.###########################.#.###########.#####.#.#.#######.#.###.#######.###.#.#.#######.#.#.#.#.###.#.###.#.#########.#.#
#...#.......###.........#.....#...........#.#...#.#.#.....#.#.#...#.....#...#...#...#...#...#.#.#.#.....#...#.#...#...###...#
###.#.#####.###.#######.#.###############.#.#.#.#.#.#####.#.#.###.#####.#.###.#######.#.#.###.#.#.#########.#.###.#.#.#######
#...#.#.....#...#.......#...............#...#.#.#.#.#####.#.#.#...#.....#...#.......#.#.#...#.#...#...#...#.#.###...#.......#
#.###.#.#####.###.#####################.#####.#.#.#.#####.#.#.#.###.#######.#######.#.#.###.#.#####.#.#.#.#.#.#############.#
#.....#.....#...#.#.....#.......#.....#.#...#.#.#.#.......#...#...#.#.......#...###.#.#.###.#.###...#...#.#...#.............#
###########.###.#.#.###.#.#####.#.###.#.#.#.#.#.#.###############.#.#.#######.#.###v#.#.###.#.###.#######.#####.#############
#.....#.....###.#.#.#...#.....#.#...#...#.#.#.#.#..........##...#.#.#.#...#...#.#.>.>.#.....#.....#.......#.....#...#...#...#
#.###.#.#######.#.#.#.#######.#.###v#####.#.#.#.#############.#.#.#.#.#.#.#.###.#.#################.#######.#####.#.#.#.#.#.#
#...#.#...#...#.#.#.#.#.....#.#.#.>.>.#...#.#.#...#...#.......#.#...#...#.#.###.#.#.............#...#.....#.......#...#...#.#
###.#.###.#.#.#.#.#.#.#.###.#.#.#.###.#.###.#.###.#.#.#.###.###.#########.#.###.#.#.###########.#.###.###.#################.#
#...#.....#.#...#...#.#...#.#.#.#...#.#.###.#.#...#.#.#...#...#.#...#...#.#...#.#.#...........#...###.#...#...###...........#
#.#########.#########.###.#.#.#.###.#.#.###.#.#.###.#.###v###.#.#.#.#.#.#v###.#.#.###########.#######.#.###.#.###.###########
#...#.....#.###...#...#...#...#...#.#.#.#...#.#...#.#.#.>.>.#.#.#.#.#.#.>.>.#.#...#...........###.....#.#...#...#...........#
###.#.###.#.###.#.#.###.#########.#.#.#.#.###.###.#.#.#.###.#.#.#.#.#.#####.#.#####.#############.#####.#.#####.###########.#
#...#.#...#.....#.#...#.......#...#.#.#.#...#...#...#.#...#.#.#.#.#.#.###...#.....#...............#.....#.....#.###...#.....#
#.###.#.#########.###.#######.#.###.#.#.###.###.#####.###.#.#.#.#.#.#.###.#######.#################.#########.#.###.#.#.#####
#.#...#.#...#...#.###.....#...#...#.#.#.###...#.#.....#...#.#.#...#.#...#...#...#.###...#...........#...#####.#.###.#.#.#...#
###...#...#...#...###...#...#####...#...#...#...#.........#...#...#.....#...###...###...#...#.....#...#.........#...###...#.#
###########################################################################################################################.#
";