Witam, potrzebuję algorytm na obliczenie najkrótszej drogi, w której występują przeszkody. O ile to możliwe, muszę znaleźć najkrótszą drogę, która nie zawiera przeszkód. Jeśli takiej nie ma - wtedy wyliczam najkrótszą drogą z przeszkodami. Pierwszą część zrobiłem tj. znajdywanie najkrótszej drogi bez przeszkód, ale nie mam zielonego pojęcia jak napisać obsługiwanie przeszkód. Przykładowo w labiryncie wolne pola są oznaczone spacją, a przeszkody znakiem '#'. Czy mógłby mi ktoś wytłumaczyć jak taki algorytm zaimplementować?
PS. Przeszkody mogę omijać tylko wtedy, gdy przed przeszkodą jest wolne pole, oraz za przeszkodą.
To co dotychczas napisałem:
const int VISITED = 1;
const int EMPTY = 0;
const int LEFT = 2;
const int RIGHT = 3;
const int DOWN = 4;
const int UP = 5;
const int WALL = 6;
int graph(vector<vector<int> > board, Point start, Point end, int n, int m)
{
int count = 0;
int reallyCount = 0;
queue<Point> q;
Point p(start.x, start.y);
board[p.x][p.y] = VISITED;
q.push(start);
while(!q.empty())
{
//drawBoard(board, n, m);
count++;
p = q.front();
q.pop();
if(p == end)
{
while(board[p.x][p.y] != VISITED)
{
switch(board[p.x][p.y])
{
case LEFT: board[p.x++][p.y] = VISITED; reallyCount++; break;
case UP: board[p.x][p.y++] = VISITED; reallyCount++; break;
case RIGHT: board[p.x--][p.y] = VISITED; reallyCount++; break;
case DOWN: board[p.x][p.y--] = VISITED; reallyCount++; break;
}
}
break;
}
if(board[p.x - 1][p.y] == EMPTY)
{
Point pp(p.x - 1, p.y);
board[p.x - 1][p.y] = LEFT;
q.push(pp);
}
if(board[p.x][p.y - 1] == EMPTY)
{
Point pp(p.x, p.y - 1);
board[p.x][p.y - 1] = UP;
q.push(pp);
}
if(board[p.x + 1][p.y] == EMPTY)
{
Point pp(p.x + 1, p.y);
board[p.x + 1][p.y] = RIGHT;
q.push(pp);
}
if(board[p.x][p.y + 1] == EMPTY)
{
Point pp(p.x, p.y + 1);
board[p.x][p.y + 1] = DOWN;
q.push(pp);
}
}
return (reallyCount > 0) ? reallyCount : -1;
}
Struktura Point przechowuje współrzędne punktu X i Y.
Proszę o pomoc.