Problem 83 "Path sum: four ways"
NOTE: This problem is a significantly more challenging version of Problem 81.
In the 5 by 5 matrix below, the minimal path sum from the top left to the bottom right, by moving left, right, up, and down, is indicated in bold red and is equal to 2297.
$$
\begin{pmatrix}
\color{red}{131} & 673 & \color{red}{234} & \color{red}{103} & \color{red}{18}\\
\color{red}{201} & \color{red}{96} & \color{red}{342} & 965 & \color{red}{150}\\
630 & 803 & 746 & \color{red}{422} & \color{red}{111}\\
537 & 699 & 497 & \color{red}{121} & 956\\
805 & 732 & 524 & \color{red}{37} & \color{red}{331}
\end{pmatrix}
$$
Find the minimal path sum from the top left to the bottom right by moving left, right, up, and down in matrix.txt, a 31K text file containing an 80 by 80 matrix.
問 83 「経路の和:4方向」
注: この問題はProblem 81よりも非常に挑戦しがいがあるだろう.
下記の5次の正方行列で, 上下左右に移動し左上のセルから開始し右下のセルで終了する道を探索
今, 31Kのテキストファイルmatrix.txtには80×80の行列が書かれている. 上下左右に移動し左上のセルから開始し右下のセルで終了する道に沿った和の最小を求めよ.
Since the dataset of the question is too large, it's using a mini set.
use std::{cmp::Ordering, collections::BinaryHeap}; #[derive(Copy, Clone, Eq, PartialEq)] struct Vertex { cost: u32, xy: (usize, usize), } impl Ord for Vertex { fn cmp(&self, other: &Self) -> Ordering { other.cost.cmp(&self.cost) } } impl PartialOrd for Vertex { fn partial_cmp(&self, other: &Self) -> Option<Ordering> { Some(self.cmp(other)) } } fn update_adjacents( v: Vertex, table: &[[u32; 5]; 5], visited: &Vec<Vec<bool>>, estimations: &mut Vec<Vec<u32>>, pq: &mut BinaryHeap<Vertex>, ) { let Vertex { xy: (x, y), cost } = v; if y > 0 { let t = y - 1; if !visited[t][x] { let e = &mut estimations[t][x]; *e = std::cmp::min(*e, table[t][x] + cost); pq.push(Vertex { cost: *e, xy: (x, t), }); } } if x < table[0].len() - 1 { let t = x + 1; if !visited[y][t] { let e = &mut estimations[y][t]; *e = std::cmp::min(*e, table[y][t] + cost); pq.push(Vertex { cost: *e, xy: (t, y), }); } } if y < table.len() - 1 { let t = y + 1; if !visited[t][x] { let e = &mut estimations[t][x]; *e = std::cmp::min(*e, table[t][x] + cost); pq.push(Vertex { cost: *e, xy: (x, t), }); } } if x > 0 { let t = x - 1; if !visited[y][t] { let e = &mut estimations[y][t]; *e = std::cmp::min(*e, table[y][t] + cost); pq.push(Vertex { cost: *e, xy: (t, y), }); } } } fn suggest_next_vertex(pq: &mut BinaryHeap<Vertex>, visited: &Vec<Vec<bool>>) -> Option<Vertex> { loop { match pq.pop() { None => return None, Some(v) if !visited[v.xy.1][v.xy.0] => return Some(v), _ => (), } } } 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 (w, h) = (table[0].len(), table.len()); let mut visited = vec![vec![false; w]; h]; let mut estimations = vec![vec![u32::MAX; w]; h]; estimations[0][0] = table[0][0]; let mut pq = std::collections::BinaryHeap::<Vertex>::new(); pq.push(Vertex { cost: estimations[0][0], xy: (0, 0), }); let is_goal = |x, y| -> bool { x == w - 1 && y == h - 1 }; let min = loop { let vertex = suggest_next_vertex(&mut pq, &visited) .expect("Goal was unreachable!"); let (x, y) = vertex.xy; if is_goal(x, y) { break vertex.cost; } visited[y][x] = true; update_adjacents(vertex, &table, &visited, &mut estimations, &mut pq); }; println!("{}", min); assert_eq!(min, 2297); }
TODO: implement a primarity queue by myself
fn update_adjacents( x: usize, y: usize, table: &[[u32; 5]; 5], visited: &Vec<Vec<bool>>, estimations: &mut Vec<Vec<u32>>, ) { let cost = estimations[y][x]; if y > 0 { let t = y - 1; if !visited[t][x] { let e = &mut estimations[t][x]; *e = std::cmp::min(*e, table[t][x] + cost); } } if x < table[0].len() - 1 { let t = x + 1; if !visited[y][t] { let e = &mut estimations[y][t]; *e = std::cmp::min(*e, table[y][t] + cost); } } if y < table.len() - 1 { let t = y + 1; if !visited[t][x] { let e = &mut estimations[t][x]; *e = std::cmp::min(*e, table[t][x] + cost); } } if x > 0 { let t = x - 1; if !visited[y][t] { let e = &mut estimations[y][t]; *e = std::cmp::min(*e, table[y][t] + cost); } } } fn suggest_next_vertex( table: &[[u32; 5]; 5], visited: &Vec<Vec<bool>>, estimations: &Vec<Vec<u32>>, ) -> Option<(usize, usize)> { let mut next: Option<(usize, usize)> = None; let mut minimum_estimation = u32::MAX; for y in 0..table.len() { for x in 0..table[0].len() { if visited[y][x] { continue; } if estimations[y][x] < minimum_estimation { minimum_estimation = estimations[y][x]; next = Some((x, y)); } } } next } 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 (w, h) = (table[0].len(), table.len()); let mut visited = vec![vec![false; w]; h]; let mut estimations = vec![vec![u32::MAX; w]; h]; estimations[0][0] = table[0][0]; let is_goal = |x, y| -> bool { x == w - 1 && y == h - 1 }; let min = loop { let (x, y) = suggest_next_vertex(&table, &visited, &estimations) .expect("Goal was unreachable!"); if is_goal(x, y) { break estimations[y][x]; } visited[y][x] = true; update_adjacents(x, y, &table, &visited, &mut estimations); }; println!("{}", min); assert_eq!(min, 2297); }