Xapac | Дата: Воскресенье, 08.02.2009, 15:11 | Сообщение # 1 |
Башка вар
Группа: Администраторы
Сообщений: 168
Статус: Offline
| Волновой алгоритм поиска путей описание алгоритма нажать тут Дано 2-ч мерный массив (карта) состоящая из чисел Code int MAP[10][10]= { 0,1,0,0,0,0,0,0,0,0, 0,1,0,0,0,0,0,0,0,0, 0,0,0,1,0,0,0,0,0,0, 1,1,0,1,0,0,0,0,0,0, 0,0,0,1,0,0,0,0,0,0, 0,0,0,1,0,0,0,0,0,0, 0, 0,0,1,1,1,1,1,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,0,0,0,0,0,0,0, }; где 1 - это непроходимое(стена, или еще какое-нибуть зелье) 0 - тропа путника Code int x_b=0; int y_b=0; начальные координаты (в которых находится испытуемый) Code int to_x_b=4; int to_y_b=5; конечная точка пути. времменная карта, в которой будем рисовать весы путей Code void CreateMap(void); заполняем 0-ми tempMAP Code void FindPath(int x,int y,int to_x,int to_y,int upper); собственно сама функция заполнения поиска пути передаваемые параметры x,y начало пути, to_x,to_y конец пути, upper глубина вхождения далее получаем из временной карты путь с помощью Code void GetPathList(int x,int y,int to_x,int to_y,int upper); пример программы Code #include <stdio.h> #include <conio.h> #include <iostream> #include <math.h> #include "wintypes.h" using namespace std; #include <vector> int MAP[10][10]= { 0,1,0,0,0,0,0,0,0,0, 0,1,0,0,0,0,0,0,0,0, 0,0,0,1,0,0,0,0,0,0, 1,1,0,1,0,0,0,0,0,0, 0,0,0,1,0,0,0,0,0,0, 0,0,0,1,0,0,0,0,0,0, 0, 0,0,1,1,1,1,1,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,0,0,0,0,0,0,0, }; int x_b=0; int y_b=0; int to_x_b=4; int to_y_b=5; bool findings=false; struct my_point { int x; int y; }; vector<my_point> PathList; int tempMAP[10][10]; void CreateMap(void); void DrawMap(void); void ClearMap(void); void DrawMap_temp(void); void FindPath(int x,int y,int to_x,int to_y,int upper); void GetPathList(int x,int y,int to_x,int to_y,int upper); void main() { CreateMap(); MAP[to_x_b][to_y_b]=9; DrawMap(); FindPath(x_b,y_b,to_x_b,to_y_b,1); ClearMap(); DrawMap_temp(); findings=false; GetPathList(to_x_b,to_y_b,0,0,tempMAP[to_x_b][to_y_b]); // while(!PathList.empty()) { // point P=PathList.front(); // PathList.pop(); // cout<<P.x<<" : "<<P.y<<endl; } } void GetPathList(int x,int y,int to_x,int to_y,int upper) { if(tempMAP[x][y]!=upper)return; if(findings)return; my_point p; p.x=x; p.y=y; cout<<p.x<<" : "<<p.y<<endl; if(x==to_x&&y==to_y) {findings=true;return;} //PathList.push_back(p); cout<<p.x<<" : "<<p.y<<endl; if(x>0)GetPathList(x-1,y,to_x,to_y,upper-1); if(y>0)GetPathList(x,y-1,to_x,to_y,upper-1); if(x>0&&y>0)GetPathList(x-1,y-1,to_x,to_y,upper-1); if(x<10)GetPathList(x+1,y,to_x,to_y,upper-1); if(y<10)GetPathList(x,y+1,to_x,to_y,upper-1); if(x<10&y<10)GetPathList(x+1,y+1,to_x,to_y,upper-1); }; void FindPath(int x,int y,int to_x,int to_y,int upper) { if(upper>20)return; if(tempMAP[x][y]<=upper&&tempMAP[x][y]>0)return; if(x==to_x&&y==to_y){tempMAP[x][y]=upper;return;} if(MAP[x][y]>0)return; tempMAP[x][y]=upper; if(x>0)FindPath(x-1,y,to_x,to_y,upper+1); if(y>0)FindPath(x,y-1,to_x,to_y,upper+1); if(x>0&&y>0)FindPath(x-1,y-1,to_x,to_y,upper+1); if(y<10)FindPath(x,y+1,to_x,to_y,upper+1); if(x<10)FindPath(x+1,y,to_x,to_y,upper+1); if(y<10&&x<10)FindPath(x+1,y+1,to_x,to_y,upper+1); }; void CreateMap(void) { for(int i=0;i<10;i++) for(int l=0;l<10;l++) tempMAP[i][l]=0; }; void DrawMap(void) { for(int i=0;i<10;i++) { for(int l=0;l<10;l++) cout<<MAP[i][l]<<" "; cout<<endl; } };
void DrawMap_temp(void) { cout<<endl; for(int i=0;i<10;i++) { for(int l=0;l<10;l++) cout<<tempMAP[i][l]<<" "; cout<<endl; } }; void ClearMap(void) { for(int i=0;i<10;i++) { for(int l=0;l<10;l++) if(tempMAP[i][l]>tempMAP[to_x_b][to_y_b])tempMAP[i][l]=0; } };
|
|
| |