Problem 82 "Path sum: three ways"

NOTE: This problem is a more challenging version of Problem 81.

The minimal path sum in the 5 by 5 matrix below, by starting in any cell in the left column and finishing in any cell in the right column, and only moving up, down, and right, is indicated in red and bold; the sum is equal to 994.

$$ \begin{pmatrix} 131 & 673 & \color{red}{234} & \color{red}{103} & \color{red}{18}\\ \color{red}{201} & \color{red}{96} & \color{red}{342} & 965 & 150\\ 630 & 803 & 746 & 422 & 111\\ 537 & 699 & 497 & 121 & 956\\ 805 & 732 & 524 & 37 & 331 \end{pmatrix} $$

Find the minimal path sum from the left column to the right column in matrix.txt, a 31K text file containing an 80 by 80 matrix.

問 82 「経路の和:3方向」

注: この問題はProblem 81よりも挑戦しがいがあるだろう.

下記の5次の正方行列で, 一番左の列の任意のセルから開始し一番右の列の任意のセルで終わる道を探索する. ただし上下右にのみ移動できるものとする. 一番小さなパスは下で赤の太字で示されたものである. このときの合計は994になる.

今, 31Kのテキストファイルmatrix.txtには80×80の行列が書かれている. 一番左の列から一番右の列へ移動する際の一番小さなパスの和を求めよ.

Since the dataset of the question is too large, it's using a mini set.

fn row_internal_loop(
    col: usize,
    row: usize,
    table: &[[u32; 5]; 5],
    determineds: &Vec<u32>,
) -> u32 {
    let mut min = u32::MAX;
    {
        let mut d = 0u32;
        for r in (0..row).rev() {
            d += table[r][col];
            min = std::cmp::min(min, determineds[r] + d);
        }
    }
    min = std::cmp::min(min, determineds[row]);
    {
        let mut d = 0u32;
        for r in row + 1..table.len() {
            d += table[r][col];
            min = std::cmp::min(min, determineds[r] + d);
        }
    }
    min
}

fn main() {
    let table: [[u32; 5]; 5] = [
        [131, 673, 234, 103, 18],
        [201, 96, 342, 965, 150],
        [630, 803, 746, 422, 111],
        [537, 699, 497, 121, 956],
        [805, 732, 524, 37, 331]
    ];
    let mut determineds = vec![0u32; table.len()];
    let mut estimations = vec![0u32; table.len()];
    for col in 0..table[0].len() {
        for row in 0..table.len() {
            let min = row_internal_loop(col, row, &table, &determineds);
            estimations[row] = table[row][col] + min;
        }
        determineds.clone_from(&estimations);
    }
    let min = estimations
        .iter()
        .min()
        .map(|&m| m)
        .expect("the input table must have at least one row");

    println!("{}", min);
    assert_eq!(min, 994);
}