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;
}
在这里插入图片描述
- 发表于:
- 原文链接：https://page.om.qq.com/page/OW-OxT1fkeQh1j2Rsvqw-aNQ0
- 腾讯「腾讯云开发者社区」是腾讯内容开放平台帐号（企鹅号）传播渠道之一，根据《腾讯内容开放平台服务协议》转载发布内容。
- 如有侵权，请联系 cloudcommunity@tencent.com 删除。
相关快讯
扫码
添加站长 进交流群
领取专属 10元无门槛券
私享最新 技术干货
腾讯云开发者
