0

I'm writing a program to solve the shortest path between two points in a circuit wiring. I use the BFS(breadth search first) method. I save the path in the path array, but I find that the coordinates of the last point in the path are not what I want (sometimes the value is correct and sometimes not).So, I printed out the path array in the findPath function, which was correct, but not correct in the main function.Why?

What's wrong with my description?I am not a native English speaker and my English is not particularly good.Please point out if what I said is not clear. English retrieval ability is still poor, I do not know if this problem is repeated.If repeated please forgive me! Thank you very much!

#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: As you can see in the figure below, the path[9] output in the findPath function is different from that in the main function. enter image description here

Sometimes the results are right

enter image description here

3
  • Trick that can save you a lot of trouble setting up maps: ideone.com/ghoNW0 Commented Oct 9, 2019 at 5:20
  • 3
    My Rubber Duckie wants to know how you can get path[9] out of an array that's only valid 0..8. Commented Oct 9, 2019 at 5:28
  • @user4581301 thank your help,I have found the mistake. Commented Oct 9, 2019 at 5:52

1 Answer 1

1

Valgrind says:

==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)

you are accessing erroneous bytes (outside your allocated memory)

the line reported by valgrind is

    cout<<"path["<<i<<"]="<<path[i].x<<","<<path[i].y<<endl;
Sign up to request clarification or add additional context in comments.

5 Comments

Thank you! I found the mistake.Point *path = new Point[M]should be Point *path = new Point[M*M];
@ClancyZeng. Another option is to use std::vector. You can push_back (or emplace_back if you're compiling to one of the more recent C++Standards) Points into the vector and it will resize itself to fit.
@user4581301 Yeah, I should have used std::vector. I'll remember next time.Thany you again!
@ClancyZeng as an added bonus, vector has an at method that throws an exception if the program wanders out of bounds. The extra checking slows a program down, but it's very helpful in finding bugs like this. Once found, you go back to using []
@user4581301 Ok, I see!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.