Банк рефератов содержит более 364 тысяч рефератов, курсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.
Полнотекстовый поиск
Всего работ:
364150
Теги названий
Разделы
Авиация и космонавтика (304)
Административное право (123)
Арбитражный процесс (23)
Архитектура (113)
Астрология (4)
Астрономия (4814)
Банковское дело (5227)
Безопасность жизнедеятельности (2616)
Биографии (3423)
Биология (4214)
Биология и химия (1518)
Биржевое дело (68)
Ботаника и сельское хоз-во (2836)
Бухгалтерский учет и аудит (8269)
Валютные отношения (50)
Ветеринария (50)
Военная кафедра (762)
ГДЗ (2)
География (5275)
Геодезия (30)
Геология (1222)
Геополитика (43)
Государство и право (20403)
Гражданское право и процесс (465)
Делопроизводство (19)
Деньги и кредит (108)
ЕГЭ (173)
Естествознание (96)
Журналистика (899)
ЗНО (54)
Зоология (34)
Издательское дело и полиграфия (476)
Инвестиции (106)
Иностранный язык (62792)
Информатика (3562)
Информатика, программирование (6444)
Исторические личности (2165)
История (21320)
История техники (766)
Кибернетика (64)
Коммуникации и связь (3145)
Компьютерные науки (60)
Косметология (17)
Краеведение и этнография (588)
Краткое содержание произведений (1000)
Криминалистика (106)
Криминология (48)
Криптология (3)
Кулинария (1167)
Культура и искусство (8485)
Культурология (537)
Литература : зарубежная (2044)
Литература и русский язык (11657)
Логика (532)
Логистика (21)
Маркетинг (7985)
Математика (3721)
Медицина, здоровье (10549)
Медицинские науки (88)
Международное публичное право (58)
Международное частное право (36)
Международные отношения (2257)
Менеджмент (12491)
Металлургия (91)
Москвоведение (797)
Музыка (1338)
Муниципальное право (24)
Налоги, налогообложение (214)
Наука и техника (1141)
Начертательная геометрия (3)
Оккультизм и уфология (8)
Остальные рефераты (21697)
Педагогика (7850)
Политология (3801)
Право (682)
Право, юриспруденция (2881)
Предпринимательство (475)
Прикладные науки (1)
Промышленность, производство (7100)
Психология (8694)
психология, педагогика (4121)
Радиоэлектроника (443)
Реклама (952)
Религия и мифология (2967)
Риторика (23)
Сексология (748)
Социология (4876)
Статистика (95)
Страхование (107)
Строительные науки (7)
Строительство (2004)
Схемотехника (15)
Таможенная система (663)
Теория государства и права (240)
Теория организации (39)
Теплотехника (25)
Технология (624)
Товароведение (16)
Транспорт (2652)
Трудовое право (136)
Туризм (90)
Уголовное право и процесс (406)
Управление (95)
Управленческие науки (24)
Физика (3463)
Физкультура и спорт (4482)
Философия (7216)
Финансовые науки (4592)
Финансы (5386)
Фотография (3)
Химия (2244)
Хозяйственное право (23)
Цифровые устройства (29)
Экологическое право (35)
Экология (4517)
Экономика (20645)
Экономико-математическое моделирование (666)
Экономическая география (119)
Экономическая теория (2573)
Этика (889)
Юриспруденция (288)
Языковедение (148)
Языкознание, филология (1140)

Курсовая работа: Поиск в лабиринте

Название: Поиск в лабиринте
Раздел: Рефераты по информатике, программированию
Тип: курсовая работа Добавлен 07:30:30 21 января 2009 Похожие работы
Просмотров: 51 Комментариев: 2 Оценило: 0 человек Средний балл: 0 Оценка: неизвестно     Скачать

Курсовая работа по программированию

"Поиск в лабиринте"


Поиск в глубину:

Алгоритм


Реализация алгоритма поиска:

Поиск в лабиринте реализован поиском в глубину (рекурсивно)

Данная реализация представлена в программе классом 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;

}

}

}

// Возвращаем число доступных позиций.

returncount;

}

Поиск в лабиринте.

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.

typedefstruct _tCoords

{

int x;

int y;

} tCoords;

Тип Смежность

Объявлен как массив на 51 элемент типа tCoords

typedeftCoordssmezh[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(){};

~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);}

};

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);}

};

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();

}

class tLabirint

{

int a[51][51];

// Матрицалабиринта

tCoords path[MAX_PATH+1]; // Путь

intcolor[51][51];

// Массив цветов. Используется в поиске для помечивания позиций в лабиринте

intcount_a; // Размерность матрицы лабиринта

intcount_p; // Длинна пути. т.е. кол-во элементов в массиве path

intflag; // Эта переменная показывает достигнута конечная позиция или нет

tCoordsstart, finish; // Координаты позиций начальной и конечной

intcx, cy; // Центр экрана

intedge; // Размер ребра

intsx, sy; // Начальные координаты для рисования лабиринта

intfx, fy; // Конечные координаты для рисования лабиринта

tMyGUI *gui; // Объект класса вывода графических примитивов

public:

tLabirint(); // конструктор

~tLabirint(); // Деструктор

voidReadMatrix(); // Считать матрицу

intGetCommon(inti, intj, smezh &s); // Найти доступную позицию в лабиринте

voidDFS_Visit(inty, intx); // Просмотреть позицию в лабиринте

voidDFS(); // Поиск в глубь

voidDrawLabirint(); // Нарисовать лабиринт

voidGetCoords(); // Считать координаты начальной и конечной позиции

void Find(); // Искатьпуть

};

tLabirint::tLabirint()

{

int i, j;

flag=0;

start.x=0;

start.y=0;

finish.x=0;

finish.y=0;

for(i=1;i<=count_a;i++)

for(j=1;j<=count_a;j++)

color[i][j]=0;

for(i=1;i<=MAX_PATH;i++)

{

path[i].x=0;

path[i].y=0;

}

count_p=0;

gui = new tMyGUI();

}

tLabirint::~tLabirint()

{

delete gui;

}

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);

//Chitat' startovuyu pozitciu:X

fread(&ch,sizeof(ch), 1, f);

start.x = atoi(&ch);

fread(&ch, sizeof(ch), 1, f);

//Chitat' startovuyu pozitciu:Y

fread(&ch,sizeof(ch), 1, f);

start.y = atoi(&ch);

fread(&ch, sizeof(ch), 1, f);

//Chitat' final'nuyu pozitciu:X

fread(&ch,sizeof(ch), 1, f);

finish.x = atoi(&ch);

fread(&ch, sizeof(ch), 1, f);

//Chitat' final'nuyu pozitciu:Y

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");

}

*/

}

int tLabirint::GetCommon(int i, int j, smezh &s)

{

//struct

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)

{

count++;

s[count].x=check[k].x;

s[count].y=check[k].y;

}

}

}

return count;

}

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;

}

void tLabirint::DFS()

{

flag=0;

DFS_Visit(start.y, start.x);

}

void tLabirint::DrawLabirint()

{

int i, j;

edge=15;

cx=getmaxx() / 2;

cy=getmaxy() / 2;

sx=cx-((count_a / 2)*edge-(edge / 2));

sy=cy-((count_a / 2)*edge-(edge / 2));

fx=sx+count_a*edge;

fy=sy+count_a*edge;

setcolor(RED);

gui->Rectangle(sx, sy, fx, fy);

for(i=1;i<=count_a;i++)

gui->Line(sx+i*edge, sy, sx+i*edge, fy);

for(i=1;i<=count_a;i++)

gui->Line(sx, sy+i*edge, fx, sy+i*edge);

for(i=1;i<=count_a;i++)

{

for(j=1;j<=count_a;j++)

{

if(a[i][j]==1)

gui->Fill(sx+(j*edge)-edge / 2, sy+(i*edge)-edge / 2, RED);

}

}

}

void tLabirint::GetCoords()

{

/*

start.x=1;

start.y=1;

finish.x=5;

finish.y=4;

*/

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);

//Chitat' startovuyu pozitciu:X

fread(&ch,sizeof(ch), 1, f);

start.x = atoi(&ch);

fread(&ch, sizeof(ch), 1, f);

//Chitat' startovuyu pozitciu:Y

fread(&ch,sizeof(ch), 1, f);

start.y = atoi(&ch);

fread(&ch, sizeof(ch), 1, f);

//Chitat' final'nuyu pozitciu:X

fread(&ch,sizeof(ch), 1, f);

finish.x = atoi(&ch);

fread(&ch, sizeof(ch), 1, f);

//Chitat' final'nuyu pozitciu:Y

fread(&ch,sizeof(ch), 1, f);

finish.y = atoi(&ch);

fread(&ch, sizeof(ch), 1, f);

}

void tLabirint::Find()

{

GetCoords();

DFS();

if(flag==0)

outtextxy(20, 440, "No way!");

else

outtextxy(20, 440, "Found way!");

}

void main()

{

tLabirint *lab;

clrscr();

lab = new tLabirint();

lab->ReadMatrix();

lab->DrawLabirint();

lab->Find();

/**/

getch();

delete lab;

}

Оценить/Добавить комментарий
Имя
Оценка
Комментарии:
Где скачать еще рефератов? Здесь: letsdoit777.blogspot.com
Евгений07:29:38 19 марта 2016
Кто еще хочет зарабатывать от 9000 рублей в день "Чистых Денег"? Узнайте как: business1777.blogspot.com ! Cпециально для студентов!
19:43:13 28 ноября 2015

Работы, похожие на Курсовая работа: Поиск в лабиринте

Назад
Меню
Главная
Рефераты
Благодарности
Опрос
Станете ли вы заказывать работу за деньги, если не найдете ее в Интернете?

Да, в любом случае.
Да, но только в случае крайней необходимости.
Возможно, в зависимости от цены.
Нет, напишу его сам.
Нет, забью.



Результаты(150896)
Комментарии (1842)
Copyright © 2005-2016 BestReferat.ru bestreferat@mail.ru       реклама на сайте

Рейтинг@Mail.ru