breadth first search for shortest path code doesn't work
Why this code doesn't work? For this input:
5 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
it outputs strange number for shortest path to the given vertex but the
matrix is ok(it contains the shortest paths to every cell in the matrix).
But if i add return 1 or something else with return at the end of the
function shortest path than it outputs the correct solution. Can someone
tell me what's wrong with the code? Thanks :)
#include <iostream>
#include <queue>
using namespace std;
struct node
{
int x,y,spath,val;
}v,c;
node mat[100][100];
int dy[] = {-1,1,0,0}, dx[] = {0,0,-1,1}, n, m;
void input()
{
cin >> n >> m;
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
cin >> mat[i][j].val;
mat[i][j].spath = 0;
}
}
}
int shortest_path(node start, node end)
{
queue<node> q;
q.push(start);
mat[start.y][start.x].val = 1;
while (!q.empty())
{
v = q.front();
q.pop();
for (int i=0; i<4; i++) {
c.y = v.y + dy[i];
c.x = v.x + dx[i];
if (c.y == end.y && c.x == end.x) {
return mat[v.y][v.x].spath + 1;
}
else if (mat[c.y][c.x].val == 0 && c.y >=0 && c.y < n && c.x
>=0 && c.x < m)
{
mat[c.y][c.x].val = 1;
mat[c.y][c.x].spath = mat[v.y][v.x].spath + 1;
q.push(c);
}
}
}
}
int main()
{
node start,end;
start.x = start.y = 0;
end.y = end.x = 4;
input();
cout << shortest_path(start,end) << endl;
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
cout << mat[i][j].spath;
}
cout << endl;
}
return 0;
}
No comments:
Post a Comment