2023-03-11：给定一个N*M的二维矩阵，只由字符'O'、'X'、'S'、'E'组成，'O'表示这个地方是可通行的平地，'

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));
}

package main

import (
  "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 []node

func (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("功能测试结束")
}