2023-03-11：给定一个N*M的二维矩阵，只由字符’O’、‘X’、‘S’、'E’组成，
'O’表示这个地方是可通行的平地，
'X’表示这个地方是不可通行的障碍，
'S’表示这个地方有一个士兵，全图保证只有一个士兵，
'E’表示这个地方有一个敌人，全图保证只有一个敌人，
士兵可以在上、下、左、右四个方向上移动，
走到相邻的可通行的平地上，走一步耗费a个时间单位，
士兵从初始地点行动时，不管去哪个方向，都不用耗费转向的代价，
但是士兵在行动途中，如果需要转向，需要额外再付出b个时间单位。
返回士兵找到敌人的最少时间。
如果因为障碍怎么都找不到敌人，返回-1，
1 <= N,M <= 1000，
1 <= a,b <= 100000，
只会有一个士兵、一个敌人。
来自华为。

答案2023-03-11：

Dijkstra算法+优先级队列。

代码根据山寨版chatgpt稍做修改写的。这不得不承认chatgpt很强大，这还是山寨版的，感觉比我自己写得还要好。

以下代码是生成的rust代码，稍微做了修改。如下：

use rand::Rng;
use std::cmp::Reverse;
use std::collections::BinaryHeap;
fn random_map(n: usize, m: usize) -> Vec<Vec<char>> {let mut map = vec![vec!['O'; m]; n];for i in 0..n {for j in 0..m {if rand::thread_rng().gen_range(0, 2) == 0 {map[i][j] = 'X';}}}let si = rand::thread_rng().gen_range(0, n);let sj = rand::thread_rng().gen_range(0, m);map[si][sj] = 'S';let (mut ei, mut ej) = (si, sj);while ei == si && ej == sj {ei = rand::thread_rng().gen_range(0, n);ej = rand::thread_rng().gen_range(0, m);}map[ei][ej] = 'E';map
}fn main() {let n = 3;let m = 4;let v = 10;println!("功能测试开始");for _ in 0..2000 {let map = random_map(n, m);let a = rand::thread_rng().gen_range(1, v + 1);let b = rand::thread_rng().gen_range(1, v + 1);let ans1 = min_cost1(&map, a, b);let ans2 = min_cost2(&map, a, b);if ans1 != ans2 {println!("出错了");println!("{}", ans1);println!("{}", ans2);return;}}println!("功能测试结束");println!("性能测试开始");let n = 1000;let m = 1000;let v = 100000;let a = rand::thread_rng().gen_range(1, v + 1);let b = rand::thread_rng().gen_range(1, v + 1);let map = random_map(n, m);println!("数据规模 : {} * {}", n, m);println!("通行代价 : {}", a);println!("转向代价 : {}", b);let start = std::time::Instant::now();min_cost2(&map, a, b);let end = std::time::Instant::now();println!("运行时间 : {}毫秒", (end - start).as_millis());println!("功能测试结束");
}fn min_cost1(map: &[Vec<char>], a: i32, b: i32) -> i32 {let n = map.len();let m = map[0].len();let mut start_x = 0;let mut start_y = 0;for i in 0..n {for j in 0..m {if map[i][j] == 'S' {start_x = i;start_y = j;}}}let mut visited = vec![vec![vec![false; 4]; m]; n];let p1 = f(&map, start_x, start_y, 0, a, b, &mut visited);let p2 = f(&map, start_x, start_y, 1, a, b, &mut visited);let p3 = f(&map, start_x, start_y, 2, a, b, &mut visited);let p4 = f(&map, start_x, start_y, 3, a, b, &mut visited);let ans = p1.min(p2).min(p3).min(p4);if ans == i32::MAX {-1} else {ans - a}
}fn f(map: &[Vec<char>],si: usize,sj: usize,d: usize,a: i32,b: i32,visited: &mut Vec<Vec<Vec<bool>>>,
) -> i32 {let n = map.len();let m = map[0].len();if si >= n || sj >= m || map[si][sj] == 'X' || visited[si][sj][d] {return i32::MAX;}if map[si][sj] == 'E' {return a;}visited[si][sj][d] = true;let p0 = f(&map, si.checked_sub(1).unwrap_or(0), sj, 0, a, b, visited);let p1 = f(&map, si + 1, sj, 1, a, b, visited);let p2 = f(&map, si, sj.checked_sub(1).unwrap_or(0), 2, a, b, visited);let p3 = f(&map, si, sj + 1, 3, a, b, visited);let p0 = if d != 0 && p0 != i32::MAX { p0 + b } else { p0 };let p1 = if d != 1 && p1 != i32::MAX { p1 + b } else { p1 };let p2 = if d != 2 && p2 != i32::MAX { p2 + b } else { p2 };let p3 = if d != 3 && p3 != i32::MAX { p3 + b } else { p3 };let ans = p0.min(p1).min(p2).min(p3);visited[si][sj][d] = false;if ans == i32::MAX {ans} else {ans + a}
}fn min_cost2(map: &[Vec<char>], a: i32, b: i32) -> i32 {let n = map.len();let m = map[0].len();let mut start_x = 0;let mut start_y = 0;for i in 0..n {for j in 0..m {if map[i][j] == 'S' {start_x = i;start_y = j;}}}let mut heap = BinaryHeap::new();heap.push((Reverse(0), start_x, start_y, 0));heap.push((Reverse(0), start_x, start_y, 1));heap.push((Reverse(0), start_x, start_y, 2));heap.push((Reverse(0), start_x, start_y, 3));// (i,j,朝向)let mut visited = vec![vec![vec![false; 4]; m]; n];let mut ans = -1;while let Some((Reverse(cost), x, y, direction)) = heap.pop() {if visited[x][y][direction] {continue;}if map[x][y] == 'E' {ans = cost;break;}visited[x][y][direction] = true;add(x as i32 - 1,y as i32,0,direction,cost,a,b,map,&mut visited,&mut heap,);add(x as i32 + 1,y as i32,1,direction,cost,a,b,map,&mut visited,&mut heap,);add(x as i32,y as i32 - 1,2,direction,cost,a,b,map,&mut visited,&mut heap,);add(x as i32,y as i32 + 1,3,direction,cost,a,b,map,&mut visited,&mut heap,);}ans
}// 从(x,y, pre_d) -> (i,j,d)
// 走格子的代价a
// 转向的代价是b
// pre_c + a
fn add(i: i32,j: i32,direction: usize,pre_direction: usize,pre_cost: i32,a: i32,b: i32,map: &[Vec<char>],visited: &mut Vec<Vec<Vec<bool>>>,heap: &mut BinaryHeap<(Reverse<i32>, usize, usize, usize)>,
) {let n = map.len() as i32;let m = map[0].len() as i32;if i < 0|| i >= n|| j < 0|| j >= m|| map[i as usize][j as usize] == 'X'|| visited[i as usize][j as usize][direction]{return;}let mut cost = pre_cost + a;if direction != pre_direction {cost += b;}heap.push((Reverse(cost), i as usize, j as usize, direction));
}

以下代码是生成的golang代码，稍微做了修改。如下：

package mainimport ("container/heap""fmt""math/rand""time"
)func minCost1(mapData [][]byte, a int, b int) int {// 获取地图大小和起点位置n, m := len(mapData), len(mapData[0])startX, startY := 0, 0for i := 0; i < n; i++ {for j := 0; j < m; j++ {if mapData[i][j] == 'S' {startX, startY = i, jbreak}}}// 初始化 visited 数组visited := make([][][]bool, n)for i := range visited {visited[i] = make([][]bool, m)for j := range visited[i] {visited[i][j] = make([]bool, 4)}}// 计算从四个方向到达终点的最短距离p1 := f(mapData, startX, startY, 0, a, b, visited)p2 := f(mapData, startX, startY, 1, a, b, visited)p3 := f(mapData, startX, startY, 2, a, b, visited)p4 := f(mapData, startX, startY, 3, a, b, visited)// 返回四个方向中最小的距离ans := min(p1, min(p2, min(p3, p4)))if ans == 1<<31-1 {return -1} else {return ans - a}
}func f(mapData [][]byte, si int, sj int, d int, a int, b int, visited [][][]bool) int {// 如果出现越界、墙壁或者已经访问过的情况，返回一个大整数表示无法到达该位置if si < 0 || si == len(mapData) || sj < 0 || sj == len(mapData[0]) || mapData[si][sj] == 'X' || visited[si][sj][d] {return 1<<31 - 1}// 如果到达终点，返回 a 表示到达终点所需的代价if mapData[si][sj] == 'E' {return a}// 标记该位置已经被访问过visited[si][sj][d] = true// 计算从四个方向到达下一个位置所需的代价（如果可以到达的话）var p [4]intp[0] = f(mapData, si-1, sj, 0, a, b, visited)p[1] = f(mapData, si+1, sj, 1, a, b, visited)p[2] = f(mapData, si, sj-1, 2, a, b, visited)p[3] = f(mapData, si, sj+1, 3, a, b, visited)if d != 0 && p[0] != 1<<31-1 {p[0] += b}if d != 1 && p[1] != 1<<31-1 {p[1] += b}if d != 2 && p[2] != 1<<31-1 {p[2] += b}if d != 3 && p[3] != 1<<31-1 {p[3] += b}// 返回四个方向中最小的代价，并且取消对该位置的访问标记ans := min(p[0], min(p[1], min(p[2], p[3])))visited[si][sj][d] = falseif ans == 1<<31-1 {return ans} else {return ans + a}
}func min(a int, b int) int {if a < b {return a} else {return b}
}func minCost2(mapData [][]byte, a int, b int) int {// 获取地图大小和起点位置n, m := len(mapData), len(mapData[0])startX, startY := 0, 0for i := 0; i < n; i++ {for j := 0; j < m; j++ {if mapData[i][j] == 'S' {startX, startY = i, jbreak}}}// 初始化优先队列和 visited 数组h := &minHeap{}heap.Init(h)heap.Push(h, node{startX, startY, 0, 0})heap.Push(h, node{startX, startY, 1, 0})heap.Push(h, node{startX, startY, 2, 0})heap.Push(h, node{startX, startY, 3, 0})visited := make([][][]bool, n)for i := range visited {visited[i] = make([][]bool, m)for j := range visited[i] {visited[i][j] = make([]bool, 4)}}// 运行 Dijkstra 算法并返回答案ans := -1for h.Len() > 0 {cur := heap.Pop(h).(node)if visited[cur.x][cur.y][cur.dir] {continue}if mapData[cur.x][cur.y] == 'E' {ans = cur.costbreak}visited[cur.x][cur.y][cur.dir] = trueadd(cur.x-1, cur.y, 0, cur.dir, cur.cost, a, b, mapData, visited, h)add(cur.x+1, cur.y, 1, cur.dir, cur.cost, a, b, mapData, visited, h)add(cur.x, cur.y-1, 2, cur.dir, cur.cost, a, b, mapData, visited, h)add(cur.x, cur.y+1, 3, cur.dir, cur.cost, a, b, mapData, visited, h)}return ans
}type node struct {x, y, dir, cost int
}type minHeap []nodefunc (h minHeap) Len() int { return len(h) }func (h minHeap) Less(i, j int) bool { return h[i].cost < h[j].cost }func (h minHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }func (h *minHeap) Push(x interface{}) { *h = append(*h, x.(node)) }func (h *minHeap) Pop() interface{} {old := *hn := len(old)x := old[n-1]*h = old[:n-1]return x
}func add(i, j, d, preD, preC, a, b int, mapData [][]byte, visited [][][]bool, h *minHeap) {if i < 0 || i == len(mapData) || j < 0 || j == len(mapData[0]) || mapData[i][j] == 'X' || visited[i][j][d] {return}cost := preC + aif d != preD {cost += b}heap.Push(h, node{i, j, d, cost})
}func randomMap(n, m int) [][]byte {mapData := make([][]byte, n)for i := range mapData {mapData[i] = make([]byte, m)for j := range mapData[i] {if rand.Float32() < 0.5 {mapData[i][j] = 'O'} else {mapData[i][j] = 'X'}}}si := rand.Intn(n)sj := rand.Intn(m)mapData[si][sj] = 'S'var ei, ej intfor {ei = rand.Intn(n)ej = rand.Intn(m)if ei != si || ej != sj {break}}mapData[ei][ej] = 'E'return mapData
}func main() {n, m := 3, 4v := 10fmt.Println("功能测试开始")for i := 0; i < 2000; i++ {mapData := randomMap(n, m)a := rand.Intn(v) + 1b := rand.Intn(v) + 1ans1 := minCost1(mapData, a, b)ans2 := minCost2(mapData, a, b)if ans1 != ans2 {fmt.Println("出错了")fmt.Println(ans1)fmt.Println(ans2)}}fmt.Println("功能测试结束")fmt.Println("性能测试开始")n = 1000m = 1000v = 100000a := rand.Intn(v) + 1b := rand.Intn(v) + 1mapData := randomMap(n, m)fmt.Println("数据规模 : ", n, " * ", m)fmt.Println("通行代价 : ", a)fmt.Println("转向代价 : ", b)start := time.Now()minCost2(mapData, a, b)end := time.Now()fmt.Println("运行时间 : ", end.Sub(start))fmt.Println("功能测试结束")
}