Witam!
Muszę napisać program wyznaczający drogę robota, którego zadaniem jest dotarcie z pkt A do B na mapie z 8x4 losowo wybieranyach segmentów (mogą się powtarzać).
Segmenty są 5x5, zbudowane z czarnych i białych pól.
Robot może poruszać się po białych polach.
Pkt A i B są rozmieszczane losowo.
Muszę zastosować algorytm Dijkstry, tylko nie wiem jak miałby wyglądać graf i realizacja programu na tym algorytmie, bo o ile ogólne zastosowanie rozumiem, tak tutaj nic nie mogę wymyślić. Co więcej program ma być na zmiennych dynamicznych i wskaźnikach oraz nie można stosować szablonów stl.
Proszę o pomoc.
0
1
Ale gdzie masz problem? Przecież masz jasno podaną strukturę grafu - tam gdzie są białe pola masz krawędzie po których możesz się poruszać.
0
Nie czaję jak dobrać te wagi.
0
Nie rozumiem jak mam dobrać wagi, aby droga była najkrótsza.
1
Grafem jest ta twoja tablica, Stwórz tablicę wynikową bool tb[8*5][4*5]; wypełnij aby tam gdzie ma być białe pole było true - wyjdzie ci mapa przejść.
Listę Q stwórz jako tablice punktów z podaną odległością (x,y,distance) rozmiarem 8*5*4*5 - czyli na maksa.
Obsługujesz ją jako kopiec lub na mniejszą ocenę (wyszukujesz min przy pobraniu lub wstawiasz element przy dodawaniu).
0
Nie rozumiem drugiego pytania. Po prostu wyobraź sobie, że masz dwie drogi z punktu A do B, jedną taką która prowadzi przez 10 białych pól a drugą taką, która prowadzi przez 4 pola. Jeżeli założysz, że te pola są tej samej wielkości i koszt przechodzenia między dwoma dowolnymi jest taki sam (a takie założenie chyba jest) to logiczne, że koszt pierwszej ścieżki jest większy niż tej drugiej. Przyjmując wagę = 1 będziesz miał 10 i 4.
0
Jakoś mam problem to sobie zwizualizować, proszę o jakieś sugestie, naprowadzenie mnie.
0
bool tile[TILE_COUNT][TILE_Y][TILE_X]=
{
{ // to jest segment A
{0,0,1,0,0},
{0,1,1,0,0},
{1,1,0,1,1},
{0,1,1,1,0},
{0,0,1,0,0},
},
{ // to jest segment B
{0,0,1,1,0},
{1,0,0,1,0},
{1,1,1,1,1},
{0,1,1,1,0},
{0,0,1,1,0},
},
...
};
bool map[BASE_Y*TILE_Y][BASE_X*TILE_X];
for(size_t Y=0;Y<BASE_Y;++Y)
{
for(size_t X=0;X<BASE_X;++X)
{
size_t rnd=rand()%TILE_COUNT;
for(size_t y=0;y<TILE_Y;++y)
{
for(size_t x=0;x<TILE_X;++x)
{
map[Y*TILE_Y+y][X*TILE_X+x]=tile[rnd][y][x];
}
}
}
}
size_t ax,ay;
do
{
ay=rand()%(BASE_Y*TILE_Y);
ax=rand()%(BASE_X*TILE_X);
} while(!map[y][x]);
mapa z wylosowanych segmentów oraz wylosowany punkt A(ax,ay);
0
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <iomanip>
using namespace std;
struct start_meta
{
int wiersz_polozenia;
int kolumna_polozenia;
};
const char segmentA[5][5]={255,255,254,255,255,255,254,254,255,255,254,254,255,254,254,255,254,254,254,255,255,255,254,255,255};
const char segmentB[5][5]={255,255,254,254,255,254,255,255,254,255,254,254,254,254,254,255,254,254,254,255,255,255,254,254,255};
const char segmentC[5][5]={254,254,254,254,254,254,254,255,254,254,254,254,255,255,254,255,254,255,255,255,255,254,254,254,254};
const char segmentD[5][5]={255,255,254,254,254,255,254,254,255,254,254,254,255,254,254,254,255,254,254,255,255,254,254,255,255};
const char segmentE[5][5]={254,254,254,255,255,255,254,254,254,255,254,254,255,254,254,254,254,255,254,254,254,254,254,254,255};
const char segmentF[5][5]={255,255,254,255,255,255,255,254,255,255,254,254,254,254,254,255,255,254,255,255,255,255,254,255,255};
const int ilosc_wierszy_w_segmencie=5;
const int ilosc_kolumn_w_segmencie=5;
const int wierszy=42;
const int kolumn=22;
void losowanie_segmentow(char plansza[wierszy][kolumn], int do_losowania_segmentow, int pomoc_z_wierszami, int pomoc_z_kolumnami);
void tworzenie_planszy(char plansza[wierszy][kolumn]);
void losowanie_obiektu(char plansza[wierszy][kolumn], start_meta &obiekt);
void losowanie_robota(char plansza[wierszy][kolumn], start_meta &robot);
void tworzenie_tablicy_przejsc(int tablica_przejsc[4][(wierszy-2)*(kolumn-2)], char plansza[wierszy][kolumn]);
int main()
{
char plansza[wierszy][kolumn];
start_meta robot,obiekt;
int tablica_przejsc[4][(wierszy-2)*(kolumn-2)];
srand(time(NULL));
tworzenie_planszy(plansza);
losowanie_robota(plansza, robot);
losowanie_obiektu(plansza, obiekt);
for(int i=0 ; i<wierszy ; i++)
for(int j=0 ; j<kolumn ; j++)
{
cout<<plansza[i][j];
if(j==kolumn-1)
cout<<endl;
}
system("pause");
return 0;
}
void tworzenie_planszy(char plansza[wierszy][kolumn])
{
int do_losowania_segmentow;
int pomoc_z_wierszami;
int pomoc_z_kolumnami;
pomoc_z_wierszami=0;
pomoc_z_kolumnami=0;
for(int i=0 ; i<wierszy ; i++)
for(int j=0 ; j<kolumn ; j++)
plansza[i][j]=65;
for(int i=0 ; i<wierszy ; i++)
for(int j=0 ; j<kolumn ; j++)
{
if(i==0 && j==0) plansza[i][j]=218; //dla elementow skrajnych program przypisuje znak ktory bedzie odzwierciedlal barierke
else if(i==wierszy-1 && j==0) plansza[i][j]=192;
else if(i==0 && j==kolumn-1) plansza[i][j]=191;
else if(i==wierszy-1 && j==kolumn-1) plansza[i][j]=217;
else if((i==0 || i==wierszy-1) && (j>0 && j<kolumn-1)) plansza[i][j]=196;
else if((i>0 && i<wierszy-1) && (j==0 || j==kolumn-1)) plansza[i][j]=179;
}
for(int i=0 ; i<8 ; i++)
{
for(int j=0 ; j<4 ; j++)
{
do_losowania_segmentow=rand()%6;
losowanie_segmentow(plansza, do_losowania_segmentow, pomoc_z_wierszami, pomoc_z_kolumnami);
pomoc_z_kolumnami+=5;
}
pomoc_z_wierszami+=5;
pomoc_z_kolumnami=0;
}
}
void losowanie_segmentow(char plansza[wierszy][kolumn], int do_losowania_segmentow, int pomoc_z_wierszami, int pomoc_z_kolumnami)
{
int a,b;
for(int i=pomoc_z_wierszami+1 ; i<pomoc_z_wierszami+6 ; i++)
for(int j=pomoc_z_kolumnami+1 ; j<pomoc_z_kolumnami+6 ; j++)
{
a=i-pomoc_z_wierszami-1;
b=j-pomoc_z_kolumnami-1;
if(do_losowania_segmentow==0)
plansza[i][j]=segmentA[a][b];
else if(do_losowania_segmentow==1)
plansza[i][j]=segmentB[a][b];
else if(do_losowania_segmentow==2)
plansza[i][j]=segmentC[a][b];
else if(do_losowania_segmentow==3)
plansza[i][j]=segmentD[a][b];
else if(do_losowania_segmentow==4)
plansza[i][j]=segmentE[a][b];
else if(do_losowania_segmentow==5)
plansza[i][j]=segmentF[a][b];
}
}
void losowanie_obiektu(char plansza[wierszy][kolumn], start_meta &obiekt)
{
do{
obiekt.wiersz_polozenia=rand()%(wierszy-1)+1;
obiekt.kolumna_polozenia=rand()%(kolumn-1)+1;
}while(plansza[obiekt.wiersz_polozenia][obiekt.kolumna_polozenia]==255);
plansza[obiekt.wiersz_polozenia][obiekt.kolumna_polozenia]='B';
}
void losowanie_robota(char plansza[wierszy][kolumn], start_meta &robot)
{
do{
robot.wiersz_polozenia=rand()%(wierszy-1)+1;
robot.kolumna_polozenia=rand()%(kolumn-1)+1;
}while(plansza[robot.wiersz_polozenia][robot.kolumna_polozenia]==255);
plansza[robot.wiersz_polozenia][robot.kolumna_polozenia]='A';
}
Na tą chwilę mam tyle tylko nie wiem jak to dalej popchnąć.
0
- zapoznaj się z pojęciem formatowania kodu: http://4programmers.net/Forum/998482
- zapoznaj się z inkrementacją: http://4programmers.net/Forum/1101404
- z całą pewnością nie potrzebujesz tablicy przejść - to jednoznacznie wynika z mapy
- użycie char zamiast bool da jeszcze z magicznymi liczbami 255/254 - to jakiś chory pomysł
- nie używaj magicznych liczb:
segmentA[5][5],wierszy=42;,i<pomoc_z_wierszami+6- zadeklaruj te podstawowe wymiary 8x4 oraz 5x5 i wszędzie używaj tych stałych - pokazałem jak zbudować mapę w bardzo prosty sposób, 7 wierszy prostego kodu, przerobiłeś to na 21 wierszy z drabinką ifów i dodatkową funkcją - WTF?
Jak poprawisz to, będzie kolejna paczka.
0
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <iomanip>
using namespace std;
int main()
{
bool tile[6][5][5]=
{
{ // to jest segment A
{0,0,1,0,0},
{0,1,1,0,0},
{1,1,0,1,1},
{0,1,1,1,0},
{0,0,1,0,0},
},
{ // to jest segment B
{0,0,1,1,0},
{1,0,0,1,0},
{1,1,1,1,1},
{0,1,1,1,0},
{0,0,1,1,0},
},
{ // to jest segment C
{1,1,1,1,1},
{1,1,0,1,1},
{1,1,0,0,1},
{0,1,0,0,0},
{0,1,1,1,1},
},
{ // to jest segment D
{0,0,1,1,1},
{0,1,1,0,1},
{1,1,0,1,1},
{1,0,1,1,0},
{0,1,1,0,0},
},
{ // to jest segment E
{1,1,1,0,0},
{0,1,1,1,0},
{1,1,0,1,1},
{1,1,0,1,1},
{1,1,1,1,0},
},
{ // to jest segment F
{0,0,1,0,0},
{0,0,1,0,0},
{1,1,1,1,1},
{0,0,1,0,0},
{0,0,1,0,0},
},
};
bool map[4*5][8*5];
for(int Y=0;Y<4;++Y)
{
for(int X=0;X<8;++X)
{
int rnd=rand()%6;
for(int y=0;y<5;++y)
{
for(int x=0;x<5;++x)
{
map[Y*5+y][X*5+x]=tile[rnd][y][x];
}
}
}
}
int ax,ay;
do
{
ay=rand()%(4*5);
ax=rand()%(8*5);
} while(!map[ay][ax]);
system("pause");
return 0;
}
0
- nie używaj magicznych liczb: segmentA[5][5], wierszy=42;, i<pomoc_z_wierszami+6 - zadeklaruj te podstawowe wymiary 8x4 oraz 5x5 i wszędzie używaj tych stałych
- wylosowanie punktu docelowego to już powyżej twoich zdolności?
0
Wylosowanie to żaden problem.
0
To z czym masz teraz problem?
0
Z zastosowaniem algorytmu dijkstry
0
- Potrzebujesz zbiór
Qw którym będą zapisane punkty, na początek wybierz zwykła tablice struktur lub wskaźników, rozmiar w połowę planszy będzie na 100% wystarczający. - Potrzebujesz dla każdego białego punktu na mapie zmienną oznaczająca aktualną odległość od początkowego punktu
- Jeżeli będziesz musiał wypisać/narysować optymalną drogę (a nie tylko podać jej długość) to również potrzebujesz dla każdego białego punktu informacje skąd do tego punktu trafiliśmy, czyli wskaźnik lub struktura ze współrzędnymi.
Najlepiej Q zrobić listą wskaźników,
zaś tablice zrobić strukturą:
struct node
{
size_t y,x; /*własne współrzędne*/
unsigned distance; /*odległość*/
node *from; /* skąd przychodzimy aby uzyskać taka odległość */
bool isRoad; /*możemy tu wejść = białe pole*/
} map[BASE_Y*TILE_Y][BASE_X*TILE_X];