2023-10-28：用 go 语言，给定一个 n*m 的二维矩阵，每个位置都是字符， U、D、L、R 表示传送带的位置，会被传送到 : 上、下、左、右， . 、O 分别表示空地、目标，一定只有一个目标点，可以

作者：福大大架构师每日一题

2023-10-28
北京
本文字数：4918 字
阅读完需：约 16 分钟

2023-10-28：用 go 语言，给定一个 n*m 的二维矩阵，每个位置都是字符，

U、D、L、R 表示传送带的位置，会被传送到 : 上、下、左、右，

. 、O 分别表示空地、目标，一定只有一个目标点，

可以在空地上选择上、下、左、右四个方向的一个，

到达传送带的点会被强制移动到其指向的下一个位置。

如果越界直接结束，返回有几个点可以到达 O 点。

来自左程云。

答案 2023-10-28：

go 代码用 chatgpt 编写，不需要修改。

c++代码用讯飞星火编写，略有改动。

大体步骤如下：

首先，代码定义了两个函数 number1 和 number2，它们都接受一个二维矩阵作为输入，并返回一个整数，表示可以到达目标点 O 的点的数量。这两个函数的主要区别在于它们的搜索策略不同。number1 使用深度优先搜索（DFS）策略，而 number2 使用广度优先搜索（BFS）策略。

在 number1 函数中，首先初始化一个与输入矩阵大小相同的 visited 矩阵，用于记录每个位置是否已经被访问过。然后，遍历输入矩阵，找到第一个目标点 O，将其位置添加到队列 queue 中，并将 visited 对应位置设为 true。接下来，从队列中取出一个位置，如果该位置是目标点 O，则计数器 ans 加 1；否则，检查该位置的上下左右四个相邻位置，如果相邻位置在矩阵范围内且未被访问过，则将其添加到队列中，并将 visited 对应位置设为 true。重复这个过程，直到队列为空。最后，返回计数器 ans 的值。

在 number2 函数中，同样首先初始化一个与输入矩阵大小相同的 visited 矩阵，用于记录每个位置是否已经被访问过。然后，遍历输入矩阵，找到第一个目标点 O，将其位置添加到队列 queue 中，并将 visited 对应位置设为 true。接下来，从队列中取出一个位置，如果该位置是目标点 O，则计数器 ans 加 1；否则，检查该位置的上下左右四个相邻位置，如果相邻位置在矩阵范围内且未被访问过，则将其添加到队列中，并将 visited 对应位置设为 true。重复这个过程，直到队列为空。最后，返回计数器 ans 的值。

generateRandomMap 函数用于生成一个随机的 nm 二维矩阵，其中包含字符 U、D、L、R、.和 O。它首先创建一个大小为 nm 的二维数组 mapData，然后遍历这个数组，对于每个位置，随机选择一个字符填充。最后，将一个随机位置设置为字符 O。

在 main 函数中，首先设置随机数种子，然后进行多次测试。每次测试，调用 generateRandomMap 函数生成一个随机矩阵，然后分别调用 number1 和 number2 函数计算可以到达目标点 O 的点的数量，如果两者的结果不相等，则输出出错信息。最后，输出测试结束的信息。

总的时间复杂度为 O(nm)，因为需要遍历整个矩阵。总的额外空间复杂度为 O(nm)，因为需要存储 visited 矩阵和队列 queue。

go 完整代码如下：

package main
import (  "fmt"  "math/rand"  "time")
// 暴力方法func number1(mapData [][]byte) int {  ans := 0  n := len(mapData)  m := len(mapData[0])  visited := make([][]bool, n)  for i := 0; i < n; i++ {    visited[i] = make([]bool, m)  }  for i := 0; i < n; i++ {    for j := 0; j < m; j++ {      if dfs(mapData, i, j, visited) {        ans++      }    }  }  return ans}
// 暴力方法func dfs(mapData [][]byte, i, j int, visited [][]bool) bool {  if i < 0 || i == len(mapData) || j < 0 || j == len(mapData[0]) || visited[i][j] {    return false  }  visited[i][j] = true  ans := false  if mapData[i][j] == 'O' {    ans = true  } else {    if mapData[i][j] == 'U' {      ans = dfs(mapData, i-1, j, visited)    } else if mapData[i][j] == 'D' {      ans = dfs(mapData, i+1, j, visited)    } else if mapData[i][j] == 'L' {      ans = dfs(mapData, i, j-1, visited)    } else if mapData[i][j] == 'R' {      ans = dfs(mapData, i, j+1, visited)    } else {      ans = dfs(mapData, i-1, j, visited) || dfs(mapData, i+1, j, visited) || dfs(mapData, i, j-1, visited) || dfs(mapData, i, j+1, visited)    }  }  visited[i][j] = false  return ans}
// 正式方法func number2(mapData [][]byte) int {  n := len(mapData)  m := len(mapData[0])  visited := make([][]bool, n)  for i := 0; i < n; i++ {    visited[i] = make([]bool, m)  }  queue := make([][2]int, n*m)  l := 0  r := 0  ans := 0  for i := 0; i < n; i++ {    for j := 0; j < m; j++ {      if mapData[i][j] == 'O' {        visited[i][j] = true        queue[r][0] = i        queue[r][1] = j        r++        break      }    }  }  for l < r {    ans++    cur := queue[l]    row := cur[0]    col := cur[1]    if row-1 >= 0 && !visited[row-1][col] && (mapData[row-1][col] == 'D' || mapData[row-1][col] == '.') {      visited[row-1][col] = true      queue[r][0] = row - 1      queue[r][1] = col      r++    }    if row+1 < n && !visited[row+1][col] && (mapData[row+1][col] == 'U' || mapData[row+1][col] == '.') {      visited[row+1][col] = true      queue[r][0] = row + 1      queue[r][1] = col      r++    }    if col-1 >= 0 && !visited[row][col-1] && (mapData[row][col-1] == 'R' || mapData[row][col-1] == '.') {      visited[row][col-1] = true      queue[r][0] = row      queue[r][1] = col - 1      r++    }    if col+1 < m && !visited[row][col+1] && (mapData[row][col+1] == 'L' || mapData[row][col+1] == '.') {      visited[row][col+1] = true      queue[r][0] = row      queue[r][1] = col + 1      r++    }    l++  }  return ans}
// 生成随机地图func generateRandomMap(n, m int) [][]byte {  mapData := make([][]byte, n)  for i := 0; i < n; i++ {    mapData[i] = make([]byte, m)    for j := 0; j < m; j++ {      r := rand.Intn(5)      if r == 0 {        mapData[i][j] = 'U'      } else if r == 1 {        mapData[i][j] = 'D'      } else if r == 2 {        mapData[i][j] = 'L'      } else if r == 3 {        mapData[i][j] = 'R'      } else {        mapData[i][j] = '.'      }    }  }  mapData[rand.Intn(n)][rand.Intn(m)] = 'O'  return mapData}
func main() {  rand.Seed(time.Now().UnixMicro())  n := 10  m := 10  testTimes := 10000  fmt.Println("测试开始")  for i := 0; i < testTimes; i++ {    mapData := generateRandomMap(n, m)    ans1 := number1(mapData)    ans2 := number2(mapData)    if ans1 != ans2 {      fmt.Println("出错了!")    }  }  fmt.Println("测试结束")}

复制代码

c++完整代码如下：

#include <iostream>#include <vector>#include <queue>#include <cstdlib>#include <ctime>
using namespace std;bool dfs(vector<vector<char>>& map, int i, int j, vector<vector<bool>>& visited);
vector<vector<char>> generateRandomMap(int n, int m);// 暴力方法int number1(vector<vector<char>>& map) {    int ans = 0;    int n = map.size();    int m = map[0].size();    vector<vector<bool>> visited(n, vector<bool>(m, false));    for (int i = 0; i < map.size(); i++) {        for (int j = 0; j < map[0].size(); j++) {            if (dfs(map, i, j, visited)) {                ans++;            }        }    }    return ans;}
// 暴力方法bool dfs(vector<vector<char>>& map, int i, int j, vector<vector<bool>>& visited) {    if (i < 0 || i == map.size() || j < 0 || j == map[0].size() || visited[i][j]) {        return false;    }    visited[i][j] = true;    bool ans = false;    if (map[i][j] == 'O') {        ans = true;    }    else {        if (map[i][j] == 'U') {            ans = dfs(map, i - 1, j, visited);        }        else if (map[i][j] == 'D') {            ans = dfs(map, i + 1, j, visited);        }        else if (map[i][j] == 'L') {            ans = dfs(map, i, j - 1, visited);        }        else if (map[i][j] == 'R') {            ans = dfs(map, i, j + 1, visited);        }        else {            ans = dfs(map, i - 1, j, visited) || dfs(map, i + 1, j, visited) || dfs(map, i, j - 1, visited)                || dfs(map, i, j + 1, visited);        }    }    visited[i][j] = false;    return ans;}
// 正式方法int number2(vector<vector<char>>& map) {    int n = map.size();    int m = map[0].size();    vector<vector<bool>> visited(n, vector<bool>(m, false));    vector<pair<int, int>> queue(n * m);    int l = 0;    int r = 0;    int ans = 0;    // O在哪，目的地    for (int i = 0; i < n; i++) {        for (int j = 0; j < m; j++) {            if (map[i][j] == 'O') {                visited[i][j] = true;                queue[r++] = make_pair(i, j);                break;            }        }    }    // [] [] [] [] [] ...      // l ...... r    while (l < r) { // 队列里还有位置！        ans++;        pair<int, int> cur = queue[l++];        int row = cur.first;        int col = cur.second;        if (row - 1 >= 0 && !visited[row - 1][col] && (map[row - 1][col] == 'D' || map[row - 1][col] == '.')) {            visited[row - 1][col] = true;            queue[r++] = make_pair(row - 1, col);        }        if (row + 1 < n && !visited[row + 1][col] && (map[row + 1][col] == 'U' || map[row + 1][col] == '.')) {            visited[row + 1][col] = true;            queue[r++] = make_pair(row + 1, col);        }        if (col - 1 >= 0 && !visited[row][col - 1] && (map[row][col - 1] == 'R' || map[row][col - 1] == '.')) {            visited[row][col - 1] = true;            queue[r++] = make_pair(row, col - 1);        }        if (col + 1 < m && !visited[row][col + 1] && (map[row][col + 1] == 'L' || map[row][col + 1] == '.')) {            visited[row][col + 1] = true;            queue[r++] = make_pair(row, col + 1);        }    }    return ans;}
// 生成随机地图vector<vector<char>> generateRandomMap(int n, int m) {    vector<vector<char>> map(n, vector<char>(m));    srand(time(0));    for (int i = 0; i < n; i++) {        for (int j = 0; j < m; j++) {            int r = rand() % 5;            if (r == 0) {                map[i][j] = 'U';            }            else if (r == 1) {                map[i][j] = 'D';            }            else if (r == 2) {                map[i][j] = 'L';            }            else if (r == 3) {                map[i][j] = 'R';            }            else {                map[i][j] = '.';            }        }    }    map[rand() % n][rand() % m] = 'O';    return map;}
// 为了测试int main() {    int n = 10;    int m = 10;    int testTimes = 1000;    cout << ("测试开始") << endl;    for (int i = 0; i < testTimes; i++) {        vector<vector<char>> map = generateRandomMap(n, m);        int ans1 = number1(map);        int ans2 = number2(map);        if (ans1 != ans2) {            cout << ("出错了！") << endl;        }    }    cout << ("测试结束") << endl;    return 0;}