leetcode 305 number-of-islands-ii

number-of-islands-ii.rs

//! leetcode 305 number-of-islands-ii
//! 给你一个大小为 m x n 的二进制网格 grid 。网格表示一张地图，其中，0 表示水，1 表示陆地。
//! 最初，grid 中的所有单元格都是水单元格（即，所有单元格都是 0）。
//! 可以通过执行 addLand 操作，将某个位置的水转换成陆地。给你一个数组 positions ，
//! 其中 positions[i] = [ri, ci] 是要执行第 i 次操作的位置 (ri, ci) 。
//!
//! 返回一个整数数组 answer ，其中 answer[i] 是将单元格 (ri, ci) 转换为陆地后，地图中岛屿的数量。
//! 岛屿 的定义是被「水」包围的「陆地」，通过水平方向或者垂直方向上相邻的陆地连接而成。
//! 你可以假设地图网格的四边均被无边无际的「水」所包围。

use std::ops::{Index, IndexMut};

struct Solution;

type FlatIndex = i32;

#[allow(unused)]
impl Solution {
    pub fn num_islands2(m: i32, n: i32, positions: Vec<Vec<i32>>) -> Vec<i32> {
        fn convert_point_to_flat_index(p: &[i32], column: i32) -> FlatIndex {
            assert_eq!(p.len(), 2);
            match p {
                [x, y] => x * column + y,
                _ => panic!("impossible")
            }
        }

        fn successors(x: i32, y: i32, (max_row, max_col): (i32, i32)) -> impl Iterator<Item=i32> {
            let suc = vec![
                if x > 0 { Some([x - 1, y]) } else { None },
                if x < max_row - 1 { Some([x + 1, y]) } else { None },
                if y > 0 { Some([x, y - 1]) } else { None },
                if y < max_col - 1 { Some([x, y + 1]) } else { None },
            ];

            suc.into_iter()
                .flatten()
                .map(move |t| convert_point_to_flat_index(t.as_slice(), max_col))
        }

        // returns delta count of island,
        // positive indicates new islands formed
        // negative indicates island connected by unions
        fn mark_position_as_land(x: i32, y: i32, max_bound: (i32, i32), set: &mut DisjointSet) -> i32 {
            let (m, n) = max_bound;
            let flat_index = convert_point_to_flat_index(&[x, y], n);
            if !set.is_land(flat_index) {
                set.mark_as_land(flat_index);

                1 - successors(x, y, (m, n))
                    .filter(|i| { set.is_land(*i) && set.connect(*i, flat_index) })
                    .count() as i32
            } else {
                0
            }
        }

        let max_index: usize = m as usize * n as usize;
        let mut set = DisjointSet {
            parent: (0..max_index as i32).into_iter().collect(),
            rank: vec![1; max_index],
            land_bitmap: vec![false; max_index],
        };

        positions.iter().map(Vec::as_slice)
            .map(|point| { mark_position_as_land(point[0], point[1], (m, n), &mut set) })
            .scan(0, |acc, delta| { *acc += delta; Some(*acc)  })
            .collect()
    }
}


#[derive(Debug, PartialOrd, PartialEq, Eq)]
struct DisjointSet {
    parent: Vec<i32>,
    rank: Vec<i32>,
    land_bitmap: Vec<bool>,
}

impl DisjointSet {
    fn rank(&self, i: FlatIndex) -> i32 {
        self.rank[i as usize]
    }

    fn set_rank(&mut self, i: FlatIndex, new_height: i32) {
        self.rank[i as usize] = new_height;
    }

    fn is_land(&self, i: FlatIndex) -> bool {
        self.land_bitmap[i as usize]
    }

    fn mark_as_land(&mut self, i: FlatIndex) {
        self.land_bitmap[i as usize] = true;
    }

    fn root(&self, index: FlatIndex) -> i32 {
        let mut p = index;
        loop {
            if self[p] == p {
                break p;
            }
            p = self[p];
        }
    }

    fn connect(&mut self, from: FlatIndex, to: FlatIndex) -> bool {
        let set = self;
        let root_i = set.root(from);
        let root_j = set.root(to);

        if root_i == root_j {
            return false;
        }

        let height_i = set.rank(root_i);
        let height_j = set.rank(root_j);

        // path compression
        if height_i > height_j {
            set[root_j] = from;
            set.set_rank(root_i, height_i + height_j);
        } else {
            set[root_i] = to;
            set.set_rank(root_j, height_j + height_i);
        }

        true
    }
}

impl Index<i32> for DisjointSet {
    type Output = i32;

    fn index(&self, index: i32) -> &Self::Output {
        if index < 0 {
            panic!("wrong index");
        }

        Index::index(&self.parent, index as usize)
    }
}

impl IndexMut<i32> for DisjointSet {
    fn index_mut(&mut self, index: i32) -> &mut i32 {
        IndexMut::index_mut(&mut self.parent, index as usize)
    }
}


#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_solution() {
        let positions = vec![
            vec![0, 0],
            vec![0, 1],
            vec![1, 2],
            vec![1, 2],
        ];

        let vec1 = Solution::num_islands2(3, 3, positions);
        assert_eq!(vec![1, 1, 2, 2], vec1)
    }
}