************************************************************************

字符串压缩

按"分割后 单数索引的地方就是需要替换的字符串

fn string_compress(string: String, dict: Vec<String>) -> String {

    // ------- " ====== " ------------ " ===== " ---- 
    let chars = string.chars();
    let mut v = vec![];
    chars.enumerate().for_each(|(idx, char)| {
        if char == '\"' {
            v.push(idx);
        }
    });
    for char in string.chars() {
        if char == '\"' {

        }
    }

    let mut flag = false;

    if string.contains('\"') {
        flag = true;    
    }

    let mut strings = string.split('\"')
                            .map(|str| str.to_string().to_ascii_lowercase())
                            .collect::<Vec<String>>();

    let mut hm = HashMap::new();
    for (idx, string) in strings.iter().enumerate() {
        if idx % 2 == 0 {
            let mut new_string = string.clone();
            for (i, word) in dict.iter().enumerate() {
                new_string = new_string.replace(word.as_str(), i.to_string().as_str());
            }
            hm.insert(idx, new_string);
            // strings[idx] = new_string;
        }
    }

    for (k, v) in hm.into_iter() {
        strings[k] = v;
    }

    if flag {
        return strings.join("\"");
    }

    strings[0].to_owned()

    // todo!()
}
fn main() {
    // let seq = [0,1,0,3,2,3];
    // println!("{}", Solution::length_of_lis(seq.to_vec()));
    let s = string_compress(
        String::from("Hello, I will go to the \"New World Park\"."), 
        // String::from("Hello, I will go to the New World Park."), 
        vec!["hello".into(), "to".into(), "park".into()]
    );
    dbg!(s);

}

士兵走出迷宫

记忆化dfs

use std::{collections::{VecDeque, HashMap}, io::SeekFrom};
/* 
    值为1时 该位置可以走通，
    值为2时 是墙，该位置无法通过，
    值为3时 为陷阱，该位置可以走通，但是要多加三个单位的时间，
    值为4时 该位置是炸弹，可以走通 而且可以把周围相邻的四堵墙炸开。*/
// static mut BEST_PATH: Box<Vec<(usize, usize)>> = Box::new();
static mut BEST_TIME: i32 = i32::MAX;
fn dfs(
    grid: &mut Vec<Vec<i32>>, 
    i: i32, 
    j: i32, 
    mut time: i32, 
    cur_path: &mut Vec<(usize, usize)>, 
    bestpath: &mut Vec<(usize, usize)>,
    visited: &mut Vec<Vec<bool>>
) {
    let m = grid.len();
    let n = grid[0].len();
    // println!("at {} {}", i, j);

    if i < 0 || i >= n as i32 || j < 0 || j >= m as i32 {
        return;
    }

    if visited[i as usize][j as usize] {
        return;
    }
    visited[i as usize][j as usize] = true;

    if grid[i as usize][j as usize] == 2 { // 墙
        return;
    }

    if grid[i as usize][j as usize] == 3 {// 陷阱
        time += 3;
    }
    
    cur_path.push((i as usize, j as usize));
    if i as usize == n - 1 && j as usize == m - 1 {
        unsafe{
            if time < BEST_TIME {
                BEST_TIME = time;
                *bestpath = cur_path.clone();
            }
        }
        return;
    }
    
    let mut restore = Vec::new();// 事后恢复炸弹的墙壁
    let mv = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    for k in 0..4 {
        let x = j + mv[k][0];
        let y = i + mv[k][1];

        if y < 0 || y >= n as i32 || x < 0 || x >= m as i32 {
            continue;
        }

        let x = x as usize;
        let y = y as usize;
        
        restore.push(
            ((x, y), grid[y][x])
        );
    }
    
    let j = j as usize;
    let i = i as usize;


    if grid[i][j] == 4 {// 炸弹
        for ((x, y), _) in restore.iter() {
            if grid[*y][*x] == 2 {
                grid[*y][*x] = 1;
            }
        }
    }

    for k in 0..4 {
        let x = j as i32 + mv[k][0];
        let y = i as i32 + mv[k][1];
        dfs(grid, y, x, time + 1, cur_path, bestpath, visited);
    }

    cur_path.pop().unwrap();
    // 恢复
    for ((x, y), r) in restore {
        grid[y][x] = r;
    }

    visited[i as usize][j as usize] = false;
}
fn main() {
    // let stdio = std::io::stdin();

    // let mut lines = String::new();
    // stdio.read_line(&mut lines).unwrap();
    // let mut lines = lines.lines();
    
    // let dime: Vec<usize> = lines.next()
    //                             .unwrap()
    //                             .split_whitespace()
    //                             .map(|x| x.parse().unwrap())
    //                             .collect();
    // let m = dime[0];
    // let n = dime[1];

    // let mut grid = Vec::new();
    // for _ in 0..m {
    //     let mut line = String::new();
    //     stdio.read_line(&mut line).unwrap();
    //     let mut lines = line.lines();

    //     let nums: Vec<u32> = lines.next()
    //                               .unwrap()
    //                               .split_whitespace()
    //                               .map(|x| x.parse().unwrap())
    //                               .collect();
    //     assert_eq!(nums.len(), n);
    //     grid.push(nums);
    // }
    // bfs(&grid, m, n);

    // ----------------------
    let mut grid = vec![
        vec![1, 2, 2, 3, 4],
        vec![1, 2, 2, 4, 2],
        vec![1, 2, 3, 1, 4],
        vec![1, 2, 3, 2, 2],
        vec![1, 1, 1, 2, 1],
    ];
    let m = 5;
    let n = 5;

    let mut cur_path = Vec::new();
    let mut bestpath = Vec::new();
    let time = 0;
    let mut visited = vec![vec![false; m]; n];
    dfs(&mut grid, 0, 0, time, &mut cur_path, &mut bestpath, &mut visited);
    // dbg!(bestpath);
    for (x, y) in bestpath {
        println!("({}, {})", x, y);
    }
}

开车到达终点的最短时长

不做hard 润！