2022-08-02：小红拿到了一个大立方体，该大立方体由111的小方块拼成，初始每个小方块都是白色

moonfdd 的个人博客 / 16 / 0 / 创建于 1年前

2022-08-02：小红拿到了一个大立方体，该大立方体由111的小方块拼成，初始每个小方块都是白色。
小红可以每次选择一个小方块染成红色，
每次小红可能选择同一个小方块重复染色，
每次染色以后，你需要帮小红回答出当前的白色连通块数，
如果两个小方块共用同一个面，且颜色相同，则它们是连通的，
给定n、m、h，表示大立方体的长、宽、高，
给定k次操作，每一次操作用(a, b, c)表示在大立方体的该位置进行染色。
返回长度为k的数组，表示每一次操作后，白色方块的连通块数。
来自网易。

答案2022-08-02：

并查集。时光倒流。

代码用rust编写。代码如下：

use rand::Rng;
fn main() {
    let size: i32 = 10;
    let test_time: i32 = 5000;
    println!("测试开始");
    for _ in 0..test_time {
        let n = rand::thread_rng().gen_range(0, size) + 1;
        let m = rand::thread_rng().gen_range(0, size) + 1;
        let h = rand::thread_rng().gen_range(0, size) + 1;
        let mut ops = random_ops(n, m, h);
        let ans1 = blocks1(n, m, h, &mut ops);
        let ans2 = blocks2(n, m, h, &mut ops);
        if ans1 != ans2 {
            println!("ans1 = {:?}", ans1);
            println!("ans2 = {:?}", ans2);
            println!("出错了!");
            break;
        }
    }
    println!("测试结束");
}

// 暴力方法
// 时间复杂度(k * n * m * h);
fn blocks1(n: i32, m: i32, h: i32, ops: &mut Vec<Vec<i32>>) -> Vec<i32> {
    let mut k = ops.len() as i32;
    //int[][][] cube = new int[n][m][h];
    let mut cube: Vec<Vec<Vec<i32>>> = vec![];
    for i in 0..n {
        cube.push(vec![]);
        for j in 0..m {
            cube[i as usize].push(vec![]);
            for _ in 0..h {
                cube[i as usize][j as usize].push(0);
            }
        }
    }
    let mut value = 1;
    let mut ans: Vec<i32> = vec![];
    for _ in 0..k {
        ans.push(0);
    }
    for i in 0..k {
        cube[ops[i as usize][0] as usize][ops[i as usize][1] as usize]
            [ops[i as usize][2] as usize] = -1;
        for x in 0..n {
            for y in 0..m {
                for z in 0..h {
                    if cube[x as usize][y as usize][z as usize] != -1
                        && cube[x as usize][y as usize][z as usize] != value
                    {
                        ans[i as usize] += 1;
                        infect(&mut cube, x, y, z, value);
                    }
                }
            }
        }
        value += 1;
    }
    return ans;
}

fn infect(cube: &mut Vec<Vec<Vec<i32>>>, a: i32, b: i32, c: i32, change: i32) {
    if a < 0
        || a == cube.len() as i32
        || b < 0
        || b == cube[0].len() as i32
        || c < 0
        || c == cube[0][0].len() as i32
        || cube[a as usize][b as usize][c as usize] == -1
        || cube[a as usize][b as usize][c as usize] == change
    {
        return;
    }
    cube[a as usize][b as usize][c as usize] = change;
    infect(cube, a - 1, b, c, change);
    infect(cube, a + 1, b, c, change);
    infect(cube, a, b - 1, c, change);
    infect(cube, a, b + 1, c, change);
    infect(cube, a, b, c - 1, change);
    infect(cube, a, b, c + 1, change);
}

// 最优解
// O(k + n * m * h)
fn blocks2(n: i32, m: i32, h: i32, ops: &mut Vec<Vec<i32>>) -> Vec<i32> {
    let mut k = ops.len() as i32;
    //int[][][] red = new int[n][m][h];
    let mut red: Vec<Vec<Vec<i32>>> = vec![];
    for i in 0..n {
        red.push(vec![]);
        for j in 0..m {
            red[i as usize].push(vec![]);
            for _ in 0..h {
                red[i as usize][j as usize].push(0);
            }
        }
    }
    for op in ops.iter() {
        red[op[0] as usize][op[1] as usize][op[2] as usize] += 1;
    }
    let mut uf = UnionFind::new(n, m, h, &mut red);
    let mut ans: Vec<i32> = vec![];
    for _ in 0..k {
        ans.push(0);
    }
    let mut i = k - 1;
    while i >= 0 {
        ans[i as usize] = uf.sets;
        let mut x = ops[i as usize][0];
        let mut y = ops[i as usize][1];
        let mut z = ops[i as usize][2];
        red[x as usize][y as usize][z as usize] -= 1;
        if red[x as usize][y as usize][z as usize] == 0 {
            // x, y ,z 这个格子，变白，建立自己的小集合
            // 然后6个方向，集合该合并合并
            uf.finger(x, y, z);
        }
        i -= 1;
    }
    return ans;
}

pub struct UnionFind {
    n: i32,
    m: i32,
    h: i32,
    father: Vec<i32>,
    size: Vec<i32>,
    help: Vec<i32>,
    sets: i32,
}
impl UnionFind {
    fn new(a: i32, b: i32, c: i32, red: &mut Vec<Vec<Vec<i32>>>) -> UnionFind {
        let mut n = a;
        let mut m = b;
        let mut h = c;
        let mut len = n * m * h;
        let mut father: Vec<i32> = vec![];
        let mut size: Vec<i32> = vec![];
        let mut help: Vec<i32> = vec![];
        for _ in 0..len {
            father.push(0);
            size.push(0);
            help.push(0);
        }
        let mut ans = UnionFind {
            n,
            m,
            h,
            father,
            size,
            help,
            sets: 0,
        };
        for x in 0..n {
            for y in 0..m {
                for z in 0..h {
                    if red[x as usize][y as usize][z as usize] == 0 {
                        ans.finger(x, y, z);
                    }
                }
            }
        }
        return ans;
    }

    pub fn finger(&mut self, x: i32, y: i32, z: i32) {
        // x，y，z
        // 一维数值
        let mut i = self.index(x, y, z);
        self.father[i as usize] = i;
        self.size[i as usize] = 1;
        self.sets += 1;
        self.union(i, x - 1, y, z);
        self.union(i, x + 1, y, z);
        self.union(i, x, y - 1, z);
        self.union(i, x, y + 1, z);
        self.union(i, x, y, z - 1);
        self.union(i, x, y, z + 1);
    }

    fn index(&mut self, x: i32, y: i32, z: i32) -> i32 {
        return z * self.n * self.m + y * self.n + x;
    }

    fn union(&mut self, mut i: i32, x: i32, y: i32, z: i32) {
        if x < 0 || x == self.n || y < 0 || y == self.m || z < 0 || z == self.h {
            return;
        }
        let mut j = self.index(x, y, z);
        if self.size[j as usize] == 0 {
            return;
        }
        i = self.find(i);
        j = self.find(j);
        if i != j {
            if self.size[i as usize] >= self.size[j as usize] {
                self.father[j as usize] = i;
                self.size[i as usize] += self.size[j as usize];
            } else {
                self.father[i as usize] = j;
                self.size[j as usize] += self.size[i as usize];
            }
            self.sets -= 1;
        }
    }

    fn find(&mut self, mut i: i32) -> i32 {
        let mut s = 0;
        while i != self.father[i as usize] {
            self.help[s] = i;
            s += 1;
            i = self.father[i as usize];
        }
        while s > 0 {
            s -= 1;
            self.father[self.help[s] as usize] = i;
        }
        return i;
    }
}

// 为了测试
fn random_ops(n: i32, m: i32, h: i32) -> Vec<Vec<i32>> {
    let mut size = rand::thread_rng().gen_range(0, n * m * h) + 1;
    let mut ans: Vec<Vec<i32>> = vec![];
    for i in 0..size {
        ans.push(vec![]);
        for _ in 0..3 {
            ans[i as usize].push(0);
        }
    }
    for i in 0..size {
        ans[i as usize][0] = rand::thread_rng().gen_range(0, n);
        ans[i as usize][1] = rand::thread_rng().gen_range(0, m);
        ans[i as usize][2] = rand::thread_rng().gen_range(0, h);
    }
    return ans;
}