2022-06-12：在NN的正方形棋盘中，有NN个棋子，那么每个格子正好可以拥有一个棋子。
但是现在有些棋子聚集到一个格子上了，比如：
2 0 3
0 1 0
3 0 0
如上的二维数组代表，一共3*3个格子，
但是有些格子有2个棋子、有些有3个、有些有1个、有些没有，
请你用棋子移动的方式，让每个格子都有一个棋子，
每个棋子可以上、下、左、右移动，每移动一步算1的代价。
返回最小的代价。
来自微软。
答案2022-06-12：
km算法，距离取负数。
代码用rust编写。代码如下：
use rand::Rng;
fn main() {
let len: i32 = 4;
let test_time: i32 = 1000;
println!("测试开始");
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!("出错了!");
println!("ans1 = {}", ans1);
println!("ans2 = {}", ans2);
println!("===============");
}
}
println!("测试结束");
}
// 暴力解
// 作为对数器
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
}
}
// 正式方法
// KM算法
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![];
// dfs过程中，碰过的点！
let mut x: Vec<bool> = vec![];
let mut y: Vec<bool> = vec![];
// 降低的预期！
// 公主上，打一个，降低预期的值，只维持最小！
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() : from王子，能不能不降预期，匹配成功！
// 能：dfs返回true！
// 不能：dfs返回false！
while !dfs(
from,
&mut x,
&mut y,
&mut lx,
&mut ly,
&mut match0,
&mut slack,
graph,
) {
// 刚才的dfs，失败了！
// 需要拿到，公主的slack里面，预期下降幅度的最小值！
let mut d = invalid;
for i in 0..nn {
if !y[i as usize] && slack[i as usize] < d {
d = slack[i as usize];
}
}
// 按照最小预期来调整预期
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();
// 然后回到while里，再次尝试
}
}
let mut ans = 0;
for i in 0..nn {
ans += lx[i as usize] + ly[i as usize];
}
return ans;
}
// from, 当前的王子
// x，王子碰没碰过
// y, 公主碰没碰过
// lx，所有王子的预期
// ly, 所有公主的预期
// match，所有公主，之前的分配，之前的爷们！
// slack，连过，但没允许的公主，最小下降的幅度
// map，报价，所有王子对公主的报价
// 返回，from号王子，不降预期能不能配成！
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] {
// 只有没dfs过的公主，才会去尝试
let d = lx[from as usize] + ly[to as usize] - map[from as usize][to as usize];
if d != 0 {
// 如果当前的路不符合预期，更新公主的slack值
slack[to as usize] = get_min(slack[to as usize], d);
} else {
// 如果当前的路符合预期，尝试直接拿下，或者抢夺让之前的安排倒腾去
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;
}
// 为了测试
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;
}
执行结果如下：
左神java代码
