2023-03-04：定义一个二维数组N*M，比如5*5数组下所示：
0, 1, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，
只能横着走或竖着走，不能斜着走，
要求编程序找出从左上角到右下角距离最短的路线。
示例输出：
[(0,0) (1,0) (2,0) (2,1) (2,2) (2,3) (2,4) (3,4) (4,4)]。
答案2023-03-04：
dijkstra算法。
代码用rust编写。代码如下：
代码语言：javascript复制use std::iter::repeat;
fn main() {
let inputs = vec![
5, 5, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0,
];
let mut ii = 0;
let n = inputs[ii];
ii = 1;
let m = inputs[ii];
ii = 1;
let mut map: Vec<Vec<i32>> = repeat(repeat(0).take(m as usize).collect())
.take(n as usize)
.collect();
for i in 0..n {
for j in 0..m {
map[i as usize][j as usize] = inputs[ii];
ii = 1;
}
}
let mut ans = dijkstra(n, m, &mut map);
ans.reverse();
println!("{:?}", ans);
}
// n : n行
// m : m列
// map :
// 0 1 1 1
// 0 0 0 1
// 1 1 0 1
// 0 0 0 0
// list = [0,0] , [1,0], [1,1]...[3,3]
// [3,3] -> [0,0]
fn dijkstra(n: i32, m: i32, map: &mut Vec<Vec<i32>>) -> Vec<Vec<i32>> {
// (a,b) -> (c,d)
// last[c][d][0] = a
// last[c][d][1] = b
// 从哪到的当前(c,d)
let mut last: Vec<Vec<Vec<i32>>> = repeat(
repeat(repeat(0).take(2).collect())
.take(m as usize)
.collect(),
)
.take(n as usize)
.collect();
// int[] arr = {c,d,w}
// 0 1 距离
//PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[2] - b[2]);
let mut heap: Vec<Vec<i32>> = vec![];
let mut visited: Vec<Vec<bool>> = repeat(repeat(false).take(m as usize).collect())
.take(n as usize)
.collect();
heap.push(vec![0, 0, 0]);
let mut ans: Vec<Vec<i32>> = vec![];
while heap.len() > 0 {
heap.sort_by(|a, b| a[2].cmp(&b[2]));
let mut cur = heap.pop().unwrap();
let x = cur[0];
let y = cur[1];
let w = cur[2];
if x == n - 1 && y == m - 1 {
break;
}
if visited[x as usize][y as usize] {
continue;
}
// (x,y)这个点
visited[x as usize][y as usize] = true;
add(
x,
y,
x - 1,
y,
w,
n,
m,
map,
&mut visited,
&mut heap,
&mut last,
);
add(
x,
y,
x 1,
y,
w,
n,
m,
map,
&mut visited,
&mut heap,
&mut last,
);
add(
x,
y,
x,
y - 1,
w,
n,
m,
map,
&mut visited,
&mut heap,
&mut last,
);
add(
x,
y,
x,
y 1,
w,
n,
m,
map,
&mut visited,
&mut heap,
&mut last,
);
}
let mut x = n - 1;
let mut y = m - 1;
while x != 0 || y != 0 {
ans.push(vec![x, y]);
let lastX = last[x as usize][y as usize][0];
let lastY = last[x as usize][y as usize][1];
x = lastX;
y = lastY;
}
ans.push(vec![0, 0]);
return ans;
}
// 当前是从(x,y) -> (i,j)
// 左上角 -> (x,y) , 距离是w
// 左上角 -> (x,y) -> (i,j) w 1
// 行一共有n行，0~n-1有效
// 列一共有m行，0~m-1有效
// map[i][j] == 1，不能走！是障碍！
// map[i][j] == 0，能走！是路！
// 把记录加入到堆里，所以得有heap
// last[i][j][0] = x
// last[i][j][1] = y
fn add(
x: i32,
y: i32,
i: i32,
j: i32,
w: i32,
n: i32,
m: i32,
map: &mut Vec<Vec<i32>>,
visited: &mut Vec<Vec<bool>>,
heap: &mut Vec<Vec<i32>>,
last: &mut Vec<Vec<Vec<i32>>>,
) {
if i >= 0
&& i < n
&& j >= 0
&& j < m
&& map[i as usize][j as usize] == 0
&& !visited[i as usize][j as usize]
{
heap.push(vec![i, j, w 1]);
last[i as usize][j as usize][0] = x;
last[i as usize][j as usize][1] = y;
}
}
