Поиск в лабиринте
Курсовая работа по программированию "Поиск в лабиринте" Поиск в глубину: Алгоритм Реализация алгоритма поиска: Поиск в лабиринте реализован поиском в глубину (рекурсивно) Данная реализация представлена в программе классом tLabirint. Условно реализацию данного алгоритма можно разбить на несколько составляющих: Считывание матрицы лабиринта из файла Нахождение доступных (смежных) позиций в лабиринте (тех мест, куда можно ходить) для каждой позиции на каждой итерации поиска. Поиск с пошаговым выводом результатов. Считывание матрицы лабиринта из файла. Матрица лабиринта хранится в виде матрицы а размерностью 51Х51. 51Х51 на мой взгляд достаточно. Формат входного файла: 1 стока: размерность матрицы лабиринта 2 строка: координата Х начальной (стартовой) позиции 3 строка: координата Y начальной (стартовой) позиции 4 строка: координата Х конечной (финальной) позиции 5 строка: координата Y конечной (финальной) позиции Затем идет матрица лабиринта размерность n символов на n строк, где n -- число из первой строки файла, размерность матрицы Причем символ «1» означает доступность клетки символ «0» означает препятствие Пример входного файла: 5 1 1 5 4 11010 01110 11100 00111 10000 void tLabirint::ReadMatrix() { FILE *f; char ch; int i,j,n; //Открываем файл f = fopen("input.txt", "rt"); // Считываем размерность fread(&ch,sizeof(ch), 1, f); // Переводим в число n = atoi(&ch); // Считываем перевод строки fread(&ch, sizeof(ch), 1, f); // Читаем стартовую позицию Х fread(&ch,sizeof(ch), 1, f); start.x = atoi(&ch); // Считываем перевод строки fread(&ch, sizeof(ch), 1, f); //Читаем стартовую позицию У fread(&ch,sizeof(ch), 1, f); start.y = atoi(&ch); // Считываем перевод строки fread(&ch, sizeof(ch), 1, f); //Читаем финальную позицию Х fread(&ch,sizeof(ch), 1, f); finish.x = atoi(&ch); // Считываем перевод строки fread(&ch, sizeof(ch), 1, f); // Читаем финальную позицию У fread(&ch,sizeof(ch), 1, f); finish.y = atoi(&ch); // Считываем перевод строки fread(&ch, sizeof(ch), 1, f); count_a=n; memset(a, 0, sizeof(a)); // Считываем матрицу лабиринта for(i=1;i<=count_a;i++) { for(j=1;j<=count_a;j++) { fread(&ch, sizeof(ch), 1, f); a[i][j]=atoi(&ch); ch=0; } // Считываем перевод строки fread(&ch, sizeof(ch), 1, f); } fclose(f); /* for(i=1;i<=count_a;i++) { for(j=1;j<=count_a;j++) printf("%d", a[i][j]); printf("\n"); } */ } Нахождение свободных мест в лабиринте. Функция берет в качестве параметров текущие координаты i, j, соответственно X и Y. Ссылку на массив координат s int tLabirint::GetCommon(int i, int j, smezh &s) { tCoords check[5]; int k, count; count=0; // Вверх check[1].x=j; check[1].y=i-1; // В право check[2].x=j+1; check[2].y=i; // Вниз check[3].x=j; check[3].y=i+1; // Влево check[4].x=j-1; check[4].y=i; for(k=1;k<=4;k++) { // Если не достигнуты границы матрицы, if((check[k].x>0) && (check[k].y>0) && (check[k].x<=count_a) && (check[k].y<=count_a)) { // То проверяем на доступность if(a[check[k].y][check[k].x]==1) { // И если позиция с координатами X, Y доступна, то добавляем к эту позицию в массив s доступных позиций count++; s[count].x=check[k].x; s[count].y=check[k].y; } } } // Возвращаем число доступных позиций. return count; } Поиск в лабиринте. void tLabirint::Find() { GetCoords(); // Получить начальные и конечные координаты DFS();//произвести поиск if(flag==0) outtextxy(20, 440, "No way!"); //Если путь не найден else outtextxy(20, 440, "Found way!"); //Если найден путь } void tLabirint::DFS() { flag=0; // Изначально нет пути DFS_Visit(start.y, start.x); // начинаем поиск } void tLabirint::DFS_Visit(int y, int x) { int i; int cnt; smezh sm; // Искомая вершина достигнута? if(flag==1) { // Если да, то выход exit; } /**/ //Красим вешину в серый цвет, т.е. начали её обработку color[y][x]=1; delay(500); count_p++; path[count_p].x=x; path[count_p].y=y; setcolor(BLUE); //defaultmouseoff; gui->Circle(sx+x*edge-edge / 2, sy+y*edge-edge / 2, 3); //defaultmouseon; //printf("X-%d;Y-%d\n", x, y); //getchar(); if((finish.x==x) && (finish.y==y)) flag=1; /**/ // Получаем координаты лабиринта, куда можно идти cnt=GetCommon(y, x, sm); for(i=1;i<=cnt;i++) { // Если позиция в лабиринте белого цвета, т.е. ещё ни разу не подвергалась обработке и если не достигнута финальная позиция if(color[sm[i].y][sm[i].x]==0 && flag==0) // Просматриваем эти координаты DFS_Visit(sm[i].y, sm[i].x); } color[y][x]=2; // Красим позицию в черный цвет, т.е. все возможные варианты у данной позиции рассмотрены. } Графический вывод В программе реализована иерархия классов для работы в графическом режиме и вывода необходимого на экран. Базовый класс. У него имеются только координаты. class tMyObj { protected: int x0, y0; public: tMyObj(){}; ~tMyObj(){}; tMyObj(int _x, int _y){x0=_x;y0=_y;}; }; Класс линия Это производный класс, он имеет к тому же две пары координат( начальная и конечная точки). class tMyLine:public tMyObj { int x1, y1; public: tMyLine(){}; ~tMyLine(){}; tMyLine(int _x, int _y, int _x1, int _y1):tMyObj(_x, _y){x1=_x1;y1=_y1;}; void Show(){line(x0, y0, x1, y1);}; void Hide(){int o = getcolor();int b = getbkcolor();setcolor(b);Show();setcolor(o);} }; Класс окружность. Это производный от базового класса tMyObj класс. Он имеет кроме координат радуис. class tMyCircle:public tMyObj { int rad; public: tMyCircle(){}; ~tMyCircle(){}; tMyCircle(int _x, int _y, int _rad):tMyObj(_x, _y){rad=_rad;}; void Show(){circle(x0, y0, rad);} }; Класс прямоугольник. Это производный от базового класса tMyObj класс имеет две пары координат (Левую верхнюю и правую нижнюю точки) class tMyRect:public tMyObj { int x1, y1; public: tMyRect(){}; ~tMyRect(){}; tMyRect(int _x, int _y, int _x1, int _y1):tMyObj(_x, _y){x1=_x1;y1=_y1;}; void Show(){rectangle(x0, y0, x1, y1);}; void Hide(){int o = getcolor();int b = getbkcolor();setcolor(b);Show();setcolor(o);} }; Класс графических примитивов. Класс графических примитивов позволяет выводить графические объекты: линия, окружность, прямоугольник, на экран. Это достигается созданием объектов классов примитивов, т.е. объектов классов линия, окружность, прямоугольник. class tMyGUI { public: tMyGUI(); ~tMyGUI(); void Line(int x, int y, int x1, int y1); void Circle(int x, int y, int rad); void Rectangle(int x, int y, int x1, int y1); void Fill(int x, int y, int Color); }; void tMyGUI::Line(int x, int y, int x1, int y1) { tMyLine tl(x, y, x1, y1); tl.Show(); } void tMyGUI::Circle(int x, int y, int rad) { tMyCircle tc(x, y, rad); tc.Show(); } void tMyGUI::Rectangle(int x, int y, int x1, int y1) { tMyRect tr(x, y, x1, y1); tr.Show(); } void tMyGUI::Fill(int x, int y, int Color) { floodfill(x, y, Color); } tMyGUI::tMyGUI() { int gdriver = DETECT, gmode, errorcode; initgraph(&gdriver, &gmode, ""); errorcode = graphresult(); if (errorcode != grOk) /* an error occurred */ { printf("Graphics error: %s\n", grapherrormsg(errorcode)); printf("Press any key to halt:"); getch(); exit(1); /* return with error code */ } } tMyGUI::~tMyGUI() { closegraph(); } Дополнительные типы данных, используемые в программе Тип координат. Представляет собой структуру с двумя полями x и y. typedef struct _tCoords { int x; int y; } tCoords; Тип Смежность Объявлен как массив на 51 элемент типа tCoords typedef tCoords smezh[51]; Константы. Максимальная длина пути. const MAX_PATH=100; Исходный текст программы: #include <stdio.h> #include <string.h> #include <stdlib.h> #include <graphics.h> #include <conio.h> #include <dos.h> typedef struct _tCoords { int x; int y; } tCoords; typedef tCoords smezh[51]; const MAX_PATH=100; class tMyObj { protected: int x0, y0; public: tMyObj(){};
Страницы: 1, 2
| 
