Поиск в ширину кода кратчайшего пути не работает

Почему этот код не работает? Для этого ввода:

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

он выводит странное число для кратчайшего пути к данной вершине, но с матрицей все в порядке (он содержит кратчайшие пути к каждой ячейке в матрице). Но если я добавлю return 1; или что-то еще с return в конце функции кратчайший путь выводит правильное решение. Может кто-нибудь сказать мне, что не так с кодом?

#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 (c.y >=0 && c.y < n && c.x >=0 && c.x < m && mat[c.y][c.x].val == 0)
{
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;
}

1

Решение

Задача ещё не решена.

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector