AOJ 0624 Food stalls

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0624

解法

bitDP で解きます．
あるマスにいるとき，それまでに買った屋台の情報を持つのですが，右か下にしかいけないことから，保存すべき場所が少なくなります．
具体的には，右，下，右上，左下の4箇所の購入状況を保存しておけば十分です．
あとは，実際に移動した時の買い方を全部試すだけで良いです．

空きマスは0円の屋台としても答えは変わらないので，そうすると一部実装がサボれるかも．

計算量は O(16 * HW)

ソースコード

fn main() {
    let cin = stdin();
    let cin = cin.lock();
    let mut sc = Scanner::new(cin);

    let h: usize = sc.read();
    let w: usize = sc.read();
    let mut map: Vec<Vec<char>> = vec![Vec::new(); h];
    for i in 0..h {
        let s: String = sc.read();
        map[i] = s.chars().collect();
    }
    let map = map;
    let mut val: Vec<Vec<i32>> = vec![vec![0; w]; h];
    for i in 0..h {
        for j in 0..w {
            if map[i][j] == '.' {
                val[i][j] = 0;
            } else {
                val[i][j] = (map[i][j].to_digit(10)).unwrap() as i32;
            }
        }
    }
    let val = val;

    let mut dp: Vec<Vec<Vec<i32>>> = vec![vec![vec![INF; 1 << 4]; w]; h];
    dp[0][0][0] = 0;
    for i in 0..h {
        for j in 0..w {
            for b in 0..(1 << 4) {
                if i + 1 < h { // go down
                    let (ny, nx) = (i + 1, j);
                    let mut pay = 0;
                    if b & (1 << 1) == 0 {
                        pay += val[ny][nx];
                    }
                    let mut v: Vec<(i32, usize)> = Vec::new();
                    let nb = 0b0110 | ((b & (1 << 2)) << 1);
                    if ny + 1 < h {
                        v.push((val[ny + 1][nx], (1 << 1)));
                        pay += val[ny + 1][nx];
                    }
                    if nx + 1 < w {
                        v.push((val[ny][nx + 1], (1 << 2)));
                        pay += val[ny][nx + 1];
                    }
                    if nx != 0 && b & (1 << 0) == 0 {
                        v.push((val[ny][nx - 1], INF as usize));
                        pay += val[ny][nx - 1];
                    }

                    if v.len() == 0 {
                        dp[ny][nx][nb] = min(dp[ny][nx][nb], dp[i][j][b] + pay);
                    }
                    for (nobuy, bb) in v {
                        let nb = if bb == INF as usize { nb } else { nb ^ bb };
                        dp[ny][nx][nb] = min(dp[ny][nx][nb], dp[i][j][b] + pay - nobuy);
                    }
                }

                if j + 1 < w { // go right
                    let (ny, nx) = (i, j + 1);
                    let mut pay = 0;
                    if b & (1 << 2) == 0 {
                        pay += val[ny][nx];
                    }
                    let mut v: Vec<(i32, usize)> = Vec::new();
                    let nb = 0b0110 | ((b & (1 << 1)) >> 1);
                    if ny + 1 < h {
                        v.push((val[ny + 1][nx], 1 << 1));
                        pay += val[ny + 1][nx];
                    }
                    if nx + 1 < w {
                        v.push((val[ny][nx + 1], 1 << 2));
                        pay += val[ny][nx + 1];
                    }
                    if ny != 0 && b & (1 << 3) == 0 {
                        v.push((val[ny - 1][nx], INF as usize));
                        pay += val[ny - 1][nx];
                    }

                    if v.len() == 0 {
                        dp[ny][nx][nb] = min(dp[ny][nx][nb], dp[i][j][b] + pay);
                    }
                    for (nobuy, bb) in v {
                        let nb = if bb == INF as usize { nb } else { nb ^ bb };
                        dp[ny][nx][nb] = min(dp[ny][nx][nb], dp[i][j][b] + pay - nobuy);
                    }
                }
            }
        }
    }
    println!("{}", dp[h - 1][w - 1].iter().min().unwrap());
}

感想

実装に若干失敗しています．右に移動する時と左に移動するときで共通処理が割りとあるので，コード量的にはもっと減らせるはずです．
が，変にまとめて混乱するよりは愚直に書いてみるかということでそうなりました．