We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Graph Theory
  4. Snakes and Ladders: The Quickest Way Up
  5. Discussions

Snakes and Ladders: The Quickest Way Up

  • marcioreisjr
     + 0 comments

    Rust is generally a bit verbose. The execution time is nice, though. time ./target/release/rust < input_1.txt (test case #1) real 0m0.016s user 0m0.006s sys 0m0.008s

    use std::collections::HashMap;
const BOARD_LEN: usize = 100;

fn quickest_way_up_dp(ii: usize, memo: &mut HashMap<usize, i32>, st: &Vec<i32>) -> Option<i32> {
    if memo.contains_key(&ii) {
        return Some(*memo.get(&ii).unwrap());
    }
    if ii == BOARD_LEN {
        return Some(0);
    }
    if ii > BOARD_LEN || st[ii] > (BOARD_LEN as i32) || st[ii] < 0 || st[ii] == ii as i32 {
        return None;
    }
    if st[ii] != 0 {
        return quickest_way_up_dp(st[ii] as usize, memo, st);
    }
    memo.insert(ii, i32::MAX);
    let mut min = i32::MAX;
    for dice in 1..=6 {
        let next = ii + dice;
        if let Some(res) = quickest_way_up_dp(next, memo, st) {
            min = min.min(res);
        }
    }
    if min != i32::MAX {
        memo.insert(ii, 1 + min);
        return Some(*memo.get(&ii).unwrap());
    }
    None
}

fn quickestWayUp(ladders: &[Vec<i32>], snakes: &[Vec<i32>]) -> i32 {
    let mut steps: Vec<i32> = vec![0; 101];
    for v in ladders {
        steps[v[0] as usize] = v[1];
    }
    for v in snakes {
        steps[v[0] as usize] = v[1];
    }
    quickest_way_up_dp(1, &mut HashMap::new(), &steps).unwrap_or(-1)
}