我正在编写一个程序来解决电路布线中两点之间的最短路径。我用的BFS(breadth search first)
方法。我把路径保存在路径数组中,但发现路径最后一个点的坐标不是我想要的(有时值正确有时不正确)。于是,我在findPath
函数中打印出了路径数组,这是正确的,但在主函数中不正确。为什么?
我的描述有什么问题?我的母语不是英语,我的英语不是特别好。如果我说的不清楚,请指出。英文检索能力还是很差,不知道这个问题有没有重复,如有重复请见谅!非常感谢你!
#include<iostream>
#include <iomanip>
#include<queue>
using namespace std;
const int M = 9;
const int MAXLEN = 30;
class Point
{
public:
int x;
int y;
};
//The increments in the x and y direction,
// in the order of up, right, down, and left
int dx[4] = {0,1,0,-1};
int dy[4] = {-1,0,1,0};
void findPath(int G[][M],Point start,Point finish,int& pathLen,Point path[])
{
//Find the shortest path from start to finish and its length, pathLen
if(start.x == finish.x && start.y == finish.y) //Two overlapping
{
pathLen = 0;
return ;
}
Point cur,next;
G[start.x][start.y] = 1; //Start of blockade
queue<int> qx,qy; //Coordinates the queue
qx.push(start.x); qy.push(start.y); //The starting point enters the queue
while(!qx.empty())
{
cur.x = qx.front(); qx.pop(); // 'cur' stands for current position
cur.y = qy.front(); qy.pop();
for(int i = 0;i < 4; i++)
{
next.x = cur.x + dx[i]; next.y = cur.y + dy[i]; // next is the next position
if(!G[next.x][next.y]) //The location is not marked
{
G[next.x][next.y] = G[cur.x][cur.y] + 1;
if(next.x == finish.x && next.y == finish.y) //Finish line
{
break;
}
qx.push(next.x);
qy.push(next.y);
}
}
if(next.x == finish.x && next.y == finish.y) break; //Finish line
}
//Structural path
pathLen = G[finish.x][finish.y];
cur = finish;
for(int i = pathLen-1; i >= 0; i--)
{
path[i] = cur; //Record current position
for(int j = 0; j < 4; j++) //Look for the previous position
{
next.x = cur.x + dx[j];
next.y = cur.y + dy[j];
if(G[next.x][next.y] > -1 && G[next.x][next.y] < G[cur.x][cur.y])
{
break;
}
}
cout<<"path["<<i<<"]="<<path[i].x<<","<<path[i].y<<endl;
cur = next; //Move to current position
}
}
int main()
{
int G[M][M]; //Grid map
Point start,finish; // The starting point and end point
int pathLen; //Shortest path length
for(int i = 0; i < M; i++) //Initializes the outer fence as -1
{
G[0][i] = G[M-1][i] = G[i][0] = G[i][M-1] = -1;
}
for(int i = 1; i < M-1; i++) //Initialize the region in the grid to 0
{
for(int j = 1; j < M-1; j++)
G[i][j] = 0;
}
G[5][1] = -1; G[6][1] = -1; G[6][2] = -1; G[6][3] = -1; G[7][1] = -1;
G[7][2] = -1; G[7][3] = -1; G[1][3] = -1; G[2][3] = -1; G[2][4] = -1;
G[3][5] = -1; G[4][4] = -1; G[4][5] = -1; G[5][5] = -1; // Inside a wall
for(int i = 0; i < M; i++) //Initial time map
{
for(int j = 0; j < M; j++)
{
cout<<setw(4)<<G[i][j];
}
cout<<endl;
}
start.x = 3; start.y = 2; finish.x = 4; finish.y = 6;
Point *path = new Point[M];
findPath(G,start,finish,pathLen,path);
for(int i = 0; i < M; i++) //Complete time map
{
for(int j = 0; j < M; j++)
{
cout<<setw(4)<<G[i][j];
}
cout<<endl;
}
for(int i = 0; i < pathLen; i++)
{
cout<<"path["<<i<<"]="<<path[i].x<<","<<path[i].y<<endl;
}
return 0;
}
output:如下图所示,函数中的path[9]
输出与findPath
函数中的输出不同main
。
有时结果是对的
Valgrind 说:
==27791== Invalid read of size 4
==27791== at 0x401B7B: main (delme.cpp:113)
==27791== Address 0x4daf108 is 0 bytes after a block of size 72 alloc'd
==27791== at 0x4839593: operator new[](unsigned long) (vg_replace_malloc.c:433)
==27791== by 0x401A03: main (delme.cpp:101)
==27791==
==27791== Invalid read of size 4
==27791== at 0x401BA6: main (delme.cpp:113)
==27791== Address 0x4daf10c is 4 bytes after a block of size 72 alloc'd
==27791== at 0x4839593: operator new[](unsigned long) (vg_replace_malloc.c:433)
==27791== by 0x401A03: main (delme.cpp:101)
您正在访问错误的字节(在分配的内存之外)
valgrind 报告的行是
cout<<"path["<<i<<"]="<<path[i].x<<","<<path[i].y<<endl;
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句