2022 - 06 - 12: dans un échiquier carré n * N, il y a n * n pièces, donc chaque pièce peut avoir exactement une pièce. Mais maintenant quelques pièces sont rassemblées sur une grille, par exemple: 2 0

2022-06-12：InNNSur un échiquier carré de,Oui.NNUn pion.,Donc chaque grille peut avoir exactement un pion.
Mais maintenant il y a des pièces qui se rassemblent sur une grille,Par exemple,：
2 0 3
0 1 0
3 0 0
Le tableau 2D ci - dessus représente,Total3*3Une grille.,
Mais certaines grilles ont2Un pion.、Certains ont3- Oui.、Certains ont1- Oui.、Certains non.,
S'il vous plaît, utilisez la façon dont les pièces se déplacent,Que chaque grille ait un pion,
Chaque pièce peut être、En bas.、Gauche.、Bouge à droite,Chaque mouvement compte1Coût.
Retour au coût minimum.
De Microsoft.

La réponse2022-06-12：

kmAlgorithmes,Distance négative.

CoderustCompilation.Les codes sont les suivants:：

use rand::Rng;
fn main() {
    
    let len: i32 = 4;
    let test_time: i32 = 1000;
    println!("Début du test");
    for _ in 0..test_time {
    
        let mut graph = random_valid_matrix(len);
        let ans1 = min_distance1(&mut graph);
        let ans2 = min_distance2(&mut graph);
        if ans1 != ans2 {
    
            println!("Une erreur s'est produite!");
            println!("ans1 = {}", ans1);
            println!("ans2 = {}", ans2);
            println!("===============");
        }
    }
    println!("Fin du test");
}

// Solution violente
//  Comme logarithme 
fn min_distance1(map: &mut Vec<Vec<i32>>) -> i32 {
    
    let mut n = 0;
    let mut m = 0;
    for i in 0..map.len() as i32 {
    
        for j in 0..map[0].len() as i32 {
    
            n += get_max(0, map[i as usize][j as usize] - 1);
            m += if map[i as usize][j as usize] == 0 {
    
                1
            } else {
    
                0
            };
        }
    }
    if n != m || n == 0 {
    
        return 0;
    }
    let mut nodes: Vec<Vec<i32>> = vec![];
    for i in 0..n {
    
        nodes.push(vec![]);
        for _ in 0..2 {
    
            nodes[i as usize].push(0);
        }
    }
    let mut space: Vec<Vec<i32>> = vec![];
    for i in 0..m {
    
        space.push(vec![]);
        for _ in 0..2 {
    
            space[i as usize].push(0);
        }
    }
    n = 0;
    m = 0;
    for i in 0..map.len() as i32 {
    
        for j in 0..map[0].len() as i32 {
    
            for _k in 2..map[i as usize][j as usize] {
    
                nodes[n as usize][0] = i;
                nodes[n as usize][1] = j;
                n += 1;
            }
            if map[i as usize][j as usize] == 0 {
    
                space[m as usize][0] = i;
                space[m as usize][1] = j;
                m += 1;
            }
        }
    }
    return process1(&mut nodes, 0, &mut space);
}

fn process1(nodes: &mut Vec<Vec<i32>>, index: i32, space: &mut Vec<Vec<i32>>) -> i32 {
    
    let mut ans = 0;
    if index == nodes.len() as i32 {
    
        for i in 0..nodes.len() as i32 {
    
            ans += distance(&mut nodes[i as usize], &mut space[i as usize]);
        }
    } else {
    
        ans = 2147483647;
        for i in index..nodes.len() as i32 {
    
            swap(nodes, index, i);
            ans = get_min(ans, process1(nodes, index + 1, space));
            swap(nodes, index, i);
        }
    }
    return ans;
}

fn swap(nodes: &mut Vec<Vec<i32>>, i: i32, j: i32) {
    
    let tmp = nodes[i as usize].clone();
    nodes[i as usize] = nodes[j as usize].clone();
    nodes[j as usize] = tmp.clone();
}

fn distance(a: &mut Vec<i32>, b: &mut Vec<i32>) -> i32 {
    
    return abs(a[0] - b[0]) + abs(a[1] - b[1]);
}
fn abs(a: i32) -> i32 {
    
    if a < 0 {
    
        -a
    } else {
    
        a
    }
}

//  Approche formelle 
// KMAlgorithmes
fn min_distance2(map: &mut Vec<Vec<i32>>) -> i32 {
    
    let mut n = 0;
    let mut m = 0;
    for i in 0..map.len() as i32 {
    
        for j in 0..map[0].len() as i32 {
    
            n += get_max(0, map[i as usize][j as usize] - 1);
            m += if map[i as usize][j as usize] == 0 {
    
                1
            } else {
    
                0
            };
        }
    }
    if n != m || n == 0 {
    
        return 0;
    }
    let mut nodes: Vec<Vec<i32>> = vec![];
    for i in 0..n {
    
        nodes.push(vec![]);
        for _ in 0..2 {
    
            nodes[i as usize].push(0);
        }
    }
    let mut space: Vec<Vec<i32>> = vec![];
    for i in 0..m {
    
        space.push(vec![]);
        for _ in 0..2 {
    
            space[i as usize].push(0);
        }
    }
    n = 0;
    m = 0;
    for i in 0..map.len() as i32 {
    
        for j in 0..map[0].len() as i32 {
    
            for _k in 2..=map[i as usize][j as usize] {
    
                nodes[n as usize][0] = i;
                nodes[n as usize][1] = j;
                n += 1;
            }
            if map[i as usize][j as usize] == 0 {
    
                space[m as usize][0] = i;
                space[m as usize][1] = j;
                m += 1;
            }
        }
    }
    let mut graph: Vec<Vec<i32>> = vec![];
    for i in 0..n {
    
        graph.push(vec![]);
        for _ in 0..n {
    
            graph[i as usize].push(0);
        }
    }
    for i in 0..n {
    
        for j in 0..n {
    
            graph[i as usize][j as usize] =
                -distance(&mut nodes[i as usize], &mut space[j as usize]);
        }
    }
    return -km(&mut graph);
}

fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    
    if a > b {
    
        a
    } else {
    
        b
    }
}

fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    
    if a < b {
    
        a
    } else {
    
        b
    }
}

fn km(graph: &mut Vec<Vec<i32>>) -> i32 {
    
    let nn = graph.len() as i32;
    let mut match0: Vec<i32> = vec![];
    let mut lx: Vec<i32> = vec![];
    let mut ly: Vec<i32> = vec![];
    // dfsEn cours, Point touché ！
    let mut x: Vec<bool> = vec![];
    let mut y: Vec<bool> = vec![];
    //  Attentes réduites ！
    //  Princesse! ,Frappe un, Réduire la valeur attendue , Maintenir le minimum seulement ！
    let mut slack: Vec<i32> = vec![];
    let mut falsev: Vec<bool> = vec![];
    for _ in 0..nn {
    
        match0.push(0);
        lx.push(0);
        ly.push(0);
        x.push(false);
        y.push(false);
        slack.push(0);
        falsev.push(false);
    }
    let invalid = 2147483647;
    for i in 0..nn {
    
        match0[i as usize] = -1;
        lx[i as usize] = -invalid;
        for j in 0..nn {
    
            lx[i as usize] = get_max(lx[i as usize], graph[i as usize][j as usize]);
        }
        ly[i as usize] = 0;
    }
    for from in 0..nn {
    
        for i in 0..nn {
    
            slack[i as usize] = invalid;
        }
        x = falsev.clone();
        y = falsev.clone();
        // dfs() : fromLe Prince., Peut - on ne pas baisser les attentes? ,Correspondance réussie！
        // Oui.：dfsRetourtrue！
        // Je ne peux pas：dfsRetourfalse！
        while !dfs(
            from,
            &mut x,
            &mut y,
            &mut lx,
            &mut ly,
            &mut match0,
            &mut slack,
            graph,
        ) {
    
            // Tout à l'heure.dfs,J'ai échoué.！
            // Il faut l'avoir., Princesse. slackÀ l'intérieur, Réduction minimale prévue ！
            let mut d = invalid;
            for i in 0..nn {
    
                if !y[i as usize] && slack[i as usize] < d {
    
                    d = slack[i as usize];
                }
            }
            //  Ajuster les attentes en fonction des attentes minimales 
            for i in 0..nn {
    
                if x[i as usize] {
    
                    lx[i as usize] = lx[i as usize] - d;
                }
                if y[i as usize] {
    
                    ly[i as usize] = ly[i as usize] + d;
                }
            }
            x = falsev.clone();
            y = falsev.clone();
            // Et revenir àwhile- Oui.,Essaie encore.
        }
    }
    let mut ans = 0;
    for i in 0..nn {
    
        ans += lx[i as usize] + ly[i as usize];
    }
    return ans;
}

// from,  Prince actuel 
// x, Wang Zi ne l'a pas touché. 
// y,  La princesse ne l'a pas touché. 
// lx, Attentes de tous les princes 
// ly,  Les attentes de toutes les princesses 
// match, Toutes les princesses , Allocation précédente , Les hommes avant ！
// slack, Oui. , Mais pas la princesse. , Ampleur de la diminution minimale 
// map,Offre, Toutes les offres de princesses 
// Retour,from Prince. , Est - ce que les attentes ne diminuent pas? ！
fn dfs(
    from: i32,
    x: &mut Vec<bool>,
    y: &mut Vec<bool>,
    lx: &mut Vec<i32>,
    ly: &mut Vec<i32>,
    match0: &mut Vec<i32>,
    slack: &mut Vec<i32>,
    map: &mut Vec<Vec<i32>>,
) -> bool {
    
    let nn = map.len() as i32;
    x[from as usize] = true;
    for to in 0..nn {
    
        if !y[to as usize] {
    
            // Seulement sidfs Une princesse passée. , Pour essayer 
            let d = lx[from as usize] + ly[to as usize] - map[from as usize][to as usize];
            if d != 0 {
    
                //  Si la route actuelle ne répond pas aux attentes , Mise à jour de la princesse slackValeur
                slack[to as usize] = get_min(slack[to as usize], d);
            } else {
    
                //  Si la route actuelle répond aux attentes , Essayez de l'enlever directement. , Ou voler et laisser tomber les arrangements précédents. 
                y[to as usize] = true;
                if match0[to as usize] == -1
                    || dfs(match0[to as usize], x, y, lx, ly, match0, slack, map)
                {
    
                    match0[to as usize] = from;
                    return true;
                }
            }
        }
    }
    return false;
}

// Pour tester
fn random_valid_matrix(len: i32) -> Vec<Vec<i32>> {
    
    let mut graph: Vec<Vec<i32>> = vec![];
    for i in 0..len {
    
        graph.push(vec![]);
        for _ in 0..len {
    
            graph[i as usize].push(0);
        }
    }
    let all = len * len;

    for _i in 1..all {
    
        graph[rand::thread_rng().gen_range(0, len) as usize]
            [rand::thread_rng().gen_range(0, len) as usize] += 1;
    }
    return graph;
}

Les résultats sont les suivants：

---

Dieu de gauche.javaCode