Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

座圧基本問題「ペンキの色」

実装演習として手を動かしてみましたが、1時間以上かかりました。実装的にハマった点が多かったので書き残しておきます。

ペンキの色 | Aizu Online Judge

問題

WxH(106)の平面にN(103)個のテープ(x1,y1,x2,y2)が重畳ありで貼ってある。この時、テープが貼ってない連続領域の個数を求めなさい。

考え方

単なる座圧です。座標の個数がN種類程度しかないので、圧縮して解くだけ。圧縮した座標系でテープを貼って、水たまり問題に帰着する。

実装

fn compress(xs: &[usize], max_v: usize) -> Vec<usize> {
    let mut v = xs.to_owned();
    v.sort();

    let mut cur = 0;
    let mut res = vec![0; max_v+1];
    for x in v {
        res[x] = cur;
        cur += 2;
    }
    res
}
fn solve() {
    input! {
        W: usize, H: usize,
        N: usize,
        X1Y1X2Y2: [(usize, usize, usize, usize); N]
    }

    let max_v = 1_000_000;
    let mut xs = vec![];
    let mut ys = vec![];
    for (x1,y1,x2,y2) in &X1Y1X2Y2 {
        xs.push(*x1); xs.push(*x2);
        ys.push(*y1); ys.push(*y2);
    }
    // dbg!(&xs, &ys);

    xs.push(0); xs.push(W);
    ys.push(0); ys.push(H);
    
    xs.sort(); xs.dedup();
    ys.sort(); ys.dedup();

    let x_compress = compress(&xs, max_v);
    let mut x_max = 0;
    for x in &x_compress {
        x_max = max(x_max, *x);
    }
    let y_compress = compress(&ys, max_v);
    let mut y_max = 0;
    for y in &y_compress {
        y_max = max(y_max, *y);
    }
    // dbg!(&x_compress, &y_compress);

    let mut mat = vec![vec![false; y_max]; x_max];
    for (x1,y1,x2,y2) in X1Y1X2Y2 {
        for x in x_compress[x1]..x_compress[x2] {
            for y in y_compress[y1]..y_compress[y2] {
                mat[x][y] = true;
            }
        }
    }
    // dbg!(&mat);

    let mut count = 0;
    loop {
        let mut found = None;
        for x in 0..x_max {
            for y in 0..y_max {
                if !mat[x][y] {
                    found = Some((x,y));
                }
            }
        }
        // dbg!(found);
        if found.is_none() {
            break;
        }
        let found = found.unwrap();

        fn rec(x: usize, y: usize, mat: &mut Vec<Vec<bool>>) -> bool {
            let x_max = mat.len();
            let y_max = mat[0].len();
            if mat[x][y] {
                return false
            }
            mat[x][y] = true;
            if x+1<x_max { rec(x+1,y,mat); }
            if y+1<y_max { rec(x,y+1,mat); }
            if x>0 { rec(x-1,y,mat); }
            if y>0 { rec(x,y-1,mat); }
            return true;
        }
        if rec(found.0, found.1, &mut mat) {
            count += 1;
        }
    }
    println!("{}", count);
}

考察

もし、テープの座標だけを使って圧縮してしまうと、端っこの貼ってない部分を無視するハメになるので、0とマックスは入れる必要があります。

    xs.push(0); xs.push(W);
    ys.push(0); ys.push(H);

重複排除するには、sortしたのちdedupを使うことが出来ます。

    xs.sort(); xs.dedup();
    ys.sort(); ys.dedup();

compressは、元の座標がせいぜい6乗なので配列を返してしまいましたが、ふつうは辞書を返した方がいい。ただ、その場合はmaxも一緒に返した方が使いやすいかも知れない。

    for x in v {
        res[x] = cur;
        cur += 2;
    }

圧縮系で2ずつ離してるのは、1にすると、元の系での空白部分が消えてしまうから。

recはクロージャにすれば、外にあるmatを食うことが出来るが、Rustのクロージャ再帰出来ないため、関数にするしかない。大抵の場合、食わせる配列は1つだからコーディング上の手間はあまりないけど、他に色々な情報を参照する必要がある場合に全部渡す必要があるとなると結構めんどくさい。

この実装では再帰でやっているけど、再帰だとスタックオーバーフローする場合もあるので、幅優先で探索した方がいいよということが蟻本には書いてある。

こういう探索だとふつう、4方向のdyを用意してloopするように書くけど、Rustの場合、usizeは負になってはいけないため、「負になってからチェックする」ということがきれいに出来ない。結構不利だと思う。

あと今見たら、foundが見つかってる時点で1カウント確定なので、recは値を返す必要がない。実際に中で使ってない。