各位程序员,今天学了bfs算法,做了走迷宫,样例测试数据过了但是一直显示运行错误!都调试一晚上了,还是找不到原因。有没有看懂的救一下我😭😭
图一,二是题目要求。
图三是显示我的样例数据通过了,答案是8没错。
图四是显示我的代码运行错误,不知道什么原因。
图五是我错误代码的编译时间和内存使用(看着也没超限制呀)
include
include
using namespace std;
struct point
{
int x;
int y;
int step;
};
queue f;
point yi(point a, int b);
int check(point a);
int n, m;
int g[100][100], v[100][100];
//迷宫矩阵,和对应的检测矩阵
//若迷宫矩阵的某位置已经走过(已经进队),则检测矩阵的该位置赋值为1
int main ()
{
cin>>n>>m;
for (int i=1; i<=n; i++)
{
for (int j=1; j<=m; j++)
cin>>g[i][j]; //输入迷宫矩阵
}
for (int i=1; i<=n; i++)
{
for (int j=1; j<=m; j++)
v[i][j] = 0; //初始化检测矩阵,全赋值为0代表搜索前全都没走过
}
point start, end; //入口坐标点,出口坐标点
int x, y;
cin>>x>>y;
start.x = x;
start.y = y;
cin>>x>>y;
end.x = x;
end.y = y; //存储入口和出口坐标
start.step = 0; //入口到入口的步数,自然为0
f.push(start); //将入口结点压入队列,
v[start.x][start.y] = 1; //并对检测矩阵的入口位置赋1表示入口已经走过了
while ( ! f.empty() ) //队列为空时结束循环
{
if ( f.front().x == end.x && f.front().y == end.y )
{
cout<<f.front().step; //队头结点为所求,输出入口到该点的步数,并结束main函数
return 0;
}
for (int i=1; i<=4; i++)
{
point p = yi ( f.front(), i ); //队头结点上下左右移动后得到的新位置
if ( check (p) )
{
p.step = f.front().step + 1;
f.push(p);
v[p.x][p.y] = 1;
}
}
f.pop();
}
cout<<-1;
return 0;
}
point yi(point a, int b) //对点坐标进行上下左右移动的函数
{
if (b==1)
a.y++;
else if (b==2)
a.y--;
else if (b==3)
a.x++;
else
a.x--;
return a;
}
int check(point a)
{
if ( a.x<1 || a.x>n || a.y<1 || a.y>m )
return 0; //该点越界,判断为不可进队
//该点不越界:
if ( g[a.x][a.y] == 1 && v[a.x][a.y] == 0 )
return 1; //该点可以走,并且没走过,判断为可进队
else
return 0; //不满足上述两个条件,判断为不可进队
}