2023-10-28：用go语言，给定一个n*m的二维矩阵，每个位置都是字符， U、D、L、R表示传送带的位置，会被传送到 :

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 

visited[i] = make([]bool, m)

}

for i := 0; i 

for j := 0; j 

if dfs(mapData, i, j, visited) {

ans++

}

}

}

return ans

}

// 暴力方法

func dfs(mapData [][]byte, i, j int, visited [][]bool) bool {

if i 

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 

visited[i] = make([]bool, m)

}

queue := make([][2]int, n*m)

l := 0

r := 0

ans := 0

for i := 0; i 

for j := 0; j 

if mapData[i][j] == 'O' {

visited[i][j] = true

queue[r][0] = i

queue[r][1] = j

r++

break

}

}

}

for l 

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 

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 

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 

mapData[i] = make([]byte, m)

for j := 0; 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 

mapData := generateRandomMap(n, m)

ans1 := number1(mapData)

ans2 := number2(mapData)

if ans1 != ans2 {

fmt.Println("出错了!")

}

}

fmt.Println("测试结束")

}

在这里插入图片描述c++完整代码如下：

#include 

#include 

#include 

#include 

#include 

using namespace std;

bool dfs(vector& map, int i, int j, vector& visited);

vector generateRandomMap(int n, int m);

// 暴力方法

int number1(vector& map) {

int ans = 0;

int n = map.size();

int m = map[0].size();

vector visited(n, vector(m, false));

for (int i = 0; i 

for (int j = 0; j 

if (dfs(map, i, j, visited)) {

ans++;

}

}

}

return ans;

}

// 暴力方法

bool dfs(vector& map, int i, int j, vector& visited) {

if (i 

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& map) {

int n = map.size();

int m = map[0].size();

vector visited(n, vector(m, false));

vector queue(n * m);

int l = 0;

int r = 0;

int ans = 0;

// O在哪，目的地

for (int i = 0; i 

for (int j = 0; j 

if (map[i][j] == 'O') {

visited[i][j] = true;

queue[r++] = make_pair(i, j);

break;

}

}

}

// [] [] [] [] [] ...

// l ...... r

while (l 

ans++;

pair 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 

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 

visited[row][col + 1] = true;

queue[r++] = make_pair(row, col + 1);

}

}

return ans;

}

// 生成随机地图

vector generateRandomMap(int n, int m) {

vector map(n, vector(m));

srand(time(0));

for (int i = 0; i 

for (int j = 0; 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 

for (int i = 0; i 

vector map = generateRandomMap(n, m);

int ans1 = number1(map);

int ans2 = number2(map);

if (ans1 != ans2) {

cout 

}

}

cout 

return 0;

}

在这里插入图片描述