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 + afn 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, 0  for i := 0; i < n; i++ {    for j := 0; j < m; j++ {      if mapData[i][j] == 'S' {        startX, startY = i, j        break      }    }  }  // 初始化 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]int  p[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] = false  if 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, 0  for i := 0; i < n; i++ {    for j := 0; j < m; j++ {      if mapData[i][j] == 'S' {        startX, startY = i, j        break      }    }  }  // 初始化优先队列和 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 := -1  for 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.cost      break    }    visited[cur.x][cur.y][cur.dir] = true    add(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 := *h  n := 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 + a  if 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 int  for {    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, 4  v := 10  fmt.Println("功能测试开始")  for i := 0; i < 2000; i++ {    mapData := randomMap(n, m)    a := rand.Intn(v) + 1    b := rand.Intn(v) + 1    ans1 := 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 = 1000  m = 1000  v = 100000  a := rand.Intn(v) + 1  b := rand.Intn(v) + 1  mapData := 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("功能测试结束")}