笔记
2026-08-21 09:02:41
发布于：浙江
2阅读
0回复
0点赞
迷宫图
建图
char g[N][N];
方向数组
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
标记数组
bool vis[N][N];
距离数组
int d[N][N];
// stl容器之一 ---- 数对
pair<int,int> p;
// 模板
void bfs(int bgx,int bgy){
queue<pair<int,int>>q;
// 初始化起点
vis[bgx][bgy]=true;
d[bgx][bgy]=0;
q.push({bgx,bgy});
while(!q.empty()){
// 取出队头
pair<int,int> t=q.front();
q.pop();
int x=t.first;
int y=t.second;
// 遍历四方向
for(int i=0;i<4;i++){
// 计算下一个位置的坐标 (nx,ny)
int nx=x+dx[i];
int ny=y+dy[i];
// 模拟 (x,y) -> (nx,ny)
// 判断是否能够走到 (nx,ny)
if(nx<1 || ny<1 || nx>n || ny>m || vis[nx][ny] || g[nx][ny]==障碍物) continue;
// 可以走到 (nx,ny)
vis[nx][ny]=true;
d[nx][ny]=d[x][y] + 1;
q.push({nx,ny});
}
}
}
bfs
迷宫图
建图
char g[N][N];
方向数组
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
标记数组
bool vis[N][N];
距离数组
int d[N][N];
// stl容器之一 ---- 数对
pair<int,int> p;
// 模板
void bfs(int bgx,int bgy){
queue<pair<int,int>>q;
// 初始化起点
vis[bgx][bgy]=true;
d[bgx][bgy]=0;
q.push({bgx,bgy});
while(!q.empty()){
// 取出队头
pair<int,int> t=q.front();
q.pop();
int x=t.first;
int y=t.second;
// 遍历四方向
for(int i=0;i<4;i++){
// 计算下一个位置的坐标 (nx,ny)
int nx=x+dx[i];
int ny=y+dy[i];
// 模拟 (x,y) -> (nx,ny)
// 判断是否能够走到 (nx,ny)
if(nx<1 || ny<1 || nx>n || ny>m || vis[nx][ny] || g[nx][ny]==障碍物) continue;
// 可以走到 (nx,ny)
vis[nx][ny]=true;
d[nx][ny]=d[x][y] + 1;
q.push({nx,ny});
}
}
}
点线图
建图
vector<int>v[N];
标记数组
bool vis[N];
距离数组
int d[N];
// 模板
void bfs(int bg){
queue<int>q;
// 初始化起点
vis[bg]=true;
d[bg]=0;
q.push(bg);
while(!q.empty()){
// 取出队头
int t=q.front();
q.pop();
// 遍历所有相邻节点
for(auto x:v[t]){
// 模拟 t -> x
// 判断是否可以走到 x
if(vis[x]) continue;
// 可以走到 x
vis[x]=true;
d[x]=d[t]+1;
q.push(x);
}
}
}
这里空空如也
有帮助，赞一个