gpt4 book ai didi

c++ - 如何在矩阵上实现 bfs?

转载 作者:塔克拉玛干 更新时间:2023-11-03 06:45:18 28 4
gpt4 key购买 nike

我在矩阵上实现 bfs 时遇到问题。似乎我的代码只检查起始节点的子节点。

我的目标是找到从“B”到“H”的最短路径。我还认为我的代码需要大量修改。先感谢您!

#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

int bfs(int, int);

bool visited[100][100];
char matrica[100][100];

int m, n, d;

int main()
{

scanf("%d %d", &m, &n);

for(int i = 0;i < m;i++){
for(int j = 0; j < n; j++){
cin >> matrica[i][j];
visited[i][j] = false;
}
}

for(int i = 0;i < m;i++){
for(int j = 0; j < n; j++){
if(matrica[i][j] == 'B'){
bfs(i, j);
}
}
}

cout << endl << d;

return 0;
}

int gk[] = {1, 0, -1, 0};
int gr[] = {0, 1, 0, -1};

int bfs(int x, int y){

cout << endl;

queue<int>queue_x, queue_y;
int topx, topy, d=0;

//memset(visited, 0, sizeof visited);

visited[x][y] = true;

queue_x.push(x);
queue_y.push(y);

while(!queue_x.empty()){
topx = queue_x.front();
topy = queue_y.front();
queue_x.pop();
queue_y.pop();

if(matrica[topx][topy] == 'H'){
cout << endl << d << endl;
d++;
return d;
}

for(int i = 0; i < 4; i++){
x += gk[i];
y += gr[i];
if(visited[x][y] == false && matrica[x][y] != '#'){
visited[x][y] = true;
matrica[x][y] = '*';
queue_x.push(x);
queue_y.push(y);
d++;

//-------------
for(int i = 0; i < m;i++){
for(int j = 0; j < n;j++){
cout << matrica[i][j];
}
cout << endl;
}
//-------------
}
}
}
}

输入/输出:

输入:

5
5
#####
#..B#
#...#
#...#
###H#

输出:

#####
#..B#
#...#
#...#
###H#
0

最佳答案

变量xy

x += gk[i];
y += gr[i];

不应该从一个迭代到下一个迭代“记住”它们的值。

将这些行更改为

x = topx + gk[i];
y = topy + gr[i];

关于c++ - 如何在矩阵上实现 bfs?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22642902/

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com