int Find(struct Lab *P,int x1,int y1,int x2, int y2)
{
int x,y,k=1,F=1;
P->Put[y2][x2]=k;
while(F)
{
F=0;
for(x=1;x<=MX;x++)
{
for(y=1;y<=MY;y++)
{
if (P->Put[y][x]==k)
{
if (P->Map[y+1][x]!=0 && P->Put[y+1][x]==0)
{ P->Put[y+1][x]=k+1;F=1;}
if (P->Map[y-1][x]!=0 && P->Put[y-1][x]==0)
{ P->Put[y-1][x]=k+1;F=1;}
if (P->Map[y][x+1]!=0 && P->Put[y][x+1]==0)
{ P->Put[y][x+1]=k+1;F=1;}
if (P->Map[y][x-1]!=0 && P->Put[y][x-1]==0)
{ P->Put[y][x-1]=k+1;F=1;}
}
}
}
k++;
}
if (P->Put[y1][x1]==0)
{
gotoxy(3,7);printf("Путь не найден");
}
else
{
gotoxy(3,7);printf("Кратчайший путь найден");
}
В модуль должна передаваться карта поля и координаты двух вершин х1,y1
и х2,y2 полученые от функции Vvod, между которыми необходимо найти
кратчайший путь.
Таблица 3 – Тесты для модуля Find
| № теста | Действие | Предполагаемое поведе- ние функции | Соответствие |
-- Критерий тестирования: покрытие решений/условий | |||
| 1 | Необходимо сформи- ровать лабиринт и ввести две вершины, между которыми необходимо найти кратчайший путь | функция должна найти путь и выдать соответствующее сообщение | полное соответствие |
| 2 | Необходимо сформи- ровать несвязаный лабиринт и ввести 2 вершины, между которыми необходи- мо найти путь | функция не должна найти путь и выдать соответст- вующее сообщение | полное соответствие |
Текст программы
#include<d:\4term\bc\bin\suslov\head.h>
void main()
{
static struct Lab P;
int X1,X2,Y1,Y2;
char a;
do{
Grin(&P);
// q(&P);
Rasstan(&P);
Vvod(&P,&X1,&Y1,&X2,&Y2);
if(!Find(&P,X1,Y1,X2,Y2))
{
gotoxy(3,7);printf("Путь не найден");
}
else
{
gotoxy(3,7);printf("Кратчайший путь:");
Puty(&P,X1,Y1,X2,Y2);
}
// q(&P);
gotoxy(3,8); printf("Press Esc to exit or any key to continue");
a=getch();
}while(a!=27);
closegraph();
}
Заголовочный файл:
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#include<graphics.h>
#include<dos.h>
const
SX=10, //координаты начала
SY=130,//
MX=30, // колво клеток по осям
MY=17,
R =20,
SetkaColor =DARKGRAY ,
RebroColor =GREEN,
UzelColor =GREEN,
CursorColor=15,
PutColor =RED ;
struct Lab
{
int Map[MY+2][MX+2];
// Карта лаб 0-непроходимо 1-дверь 2-комната
int Put[MY+2][MX+2];
// Карта прохождения 1-непроходит
};
int Grin(struct Lab* P)
{
int gdriver = DETECT,gmode, errorcode;
initgraph(&gdriver, &gmode,"");
errorcode = graphresult();
if (errorcode != grOk)
{
printf("Graphics error: %s\n", grapherrormsg(errorcode));
printf("Graphics error:Press any key:");
getch();
exit(1);
};
int x, y;
for(y=0;y<MY+2;y++)
for(x=0;x<MX+2;x++)
{
P->Map[y][x]=0; /*Инициализирует массивы*/
P->Put[y][x]=0;
}
for(y=0;y<MY+2;y++)
{
P->Put[y][0 ]=-1;
P->Put[y][MX+1]=-1;
}
for(x=0;x<MX+2;x++)
{
P->Put[0 ][x]=-1;
P->Put[MY+1][x]=-1;
}
//Setka
setcolor(SetkaColor);
for(y=0;y<=MY;y++)
for(x=0;x<=MX;x++)
{
line(SX+x*R,SY ,SX+x*R ,SY+R*MY);
line(SX ,SY+y*R,SX+MX*R,SY+y*R);
}
return 0;
}
void maska(int x,int y)
{
setcolor(0);
rectangle(SX+(x-1)*R+1,SY+(y-1)*R+1,SX+x*R-1,SY+y*R-1);
}
void vyvod(int x,int y)
{
setcolor(CursorColor);
rectangle(SX+(x-1)*R+1,SY+(y-1)*R+1,SX+x*R-1,SY+y*R-1);
}
void Rasstan(struct Lab* P)
{
int x=1 , y=1; //Коорты курсора
gotoxy(55,4); printf("Управление:");
gotoxy(55,5); printf(" я - удалить");
gotoxy(55,6); printf(" д - дверь");
gotoxy(55,7); printf(" к - комната");
gotoxy(55,8); printf(" Enter - ввести");
vyvod(x,y);
char a;
do{
a=getch();
if(!a) a=getch();
maska(x,y);
switch (a)
{
case 80 :if (y<MY) ++y ;break; /* вниз */
case 72 :if (y>1 ) --y ;break; /* вверх */
case 75 :if (x>1 ) --x ;break; /* влево */
case 77 :if (x<MX) ++x ;break; /* вправо*/
case 'z' :P->Map[y][x]=0 ;
setcolor(0);setfillstyle(1,0);
bar(SX+(x-1)*R+1,SY+(y-1)*R+1,SX+x*R-1,SY+y*R-1);
break;
//раставляем ком и дв
case 'l' :P->Map[y][x]=1 ;
setcolor(RebroColor);
line(SX+x*R-R/2,SY+(y-1)*R+1,SX+x*R-R/2,SY+y*R-1);
line(SX+(x-1)*R+1,SY+y*R-R/2,SX+x*R-1,SY+y*R-R/2);
break;
case 'r' :P->Map[y][x]=2 ;
setcolor(UzelColor);setfillstyle(1,UzelColor);
fillellipse(SX+x*R-R/2,SY+y*R-R/2,R/2-1,R/2-1);
break;
case 27 : exit(0);//vixod iz programmi
}
vyvod(x,y);
}while(a!=13);
maska(x,y);
}
void Vvod(struct Lab* P, int* x1, int* y1, int* x2, int* y2)
{
gotoxy(3,2);printf("Введите вход в лабиринт");
int x=1,y=1;
char a;
vyvod(x,y);
do{
a=getch();
if(!a) a=getch();
maska(x,y);
switch(a){
case 80 :if (y<MY) ++y ;break; /* вниз */
case 72 :if (y>1 ) --y ;break; /* вверх */
case 75 :if (x>1 ) --x ;break; /* влево */
case 77 :if (x<MX) ++x ;break; /* вправо*/
case 27 :exit(0);
}
vyvod(x,y);
if ((a==13) && (P->Map[y][x]==2)) break;
}while(1);
maska(x,y);
*x1=x;*y1=y;
gotoxy(3,3); printf("x1=%3i y1=%3i ",x,y);
gotoxy(3,4);printf("Введите выход");
vyvod(x,y);
do{
a=getch();
if(!a) a=getch();
maska(x,y);
switch(a){
case 80 :if (y<MY) ++y ;break; /* вниз */
case 72 :if (y>1 ) --y ;break; /* вверх */
case 75 :if (x>1 ) --x ;break; /* влево */
case 77 :if (x<MX) ++x ;break; /* вправо*/
case 27 :exit(0);
}
vyvod(x,y);
if ((a==13) && (P->Map[y][x]==2)) break;
}while(1);
maska(x,y);
*x2=x;*y2=y;
gotoxy(3,5); printf("x2=%3i y2=%3i ",x,y);
}
int Find(struct Lab *P,int x1,int y1,int x2, int y2)
{
int x,y,k=1,F=1;
P->Put[y2][x2]=k;
while(F)
{
F=0;
for(x=1;x<=MX;x++)
{
for(y=1;y<=MY;y++)
{
if (P->Put[y][x]==k)
{
if (P->Map[y+1][x]!=0 && P->Put[y+1][x]==0)
{ P->Put[y+1][x]=k+1;F=1;}
if (P->Map[y-1][x]!=0 && P->Put[y-1][x]==0)
{ P->Put[y-1][x]=k+1;F=1;}
if (P->Map[y][x+1]!=0 && P->Put[y][x+1]==0)
{ P->Put[y][x+1]=k+1;F=1;}
if (P->Map[y][x-1]!=0 && P->Put[y][x-1]==0)
{ P->Put[y][x-1]=k+1;F=1;}
}
}
}
k++;
}
if (P->Put[y1][x1]==0) return 0; else return 1;
}
void Puty(struct Lab* P,int x1, int y1, int x2, int y2)
{
int x=x1,y=y1;
int k;
setcolor(PutColor);
setfillstyle(1,PutColor);
while(!(x==x2 && y==y2))
{
fillellipse(SX+x*R-R/2,SY+y*R-R/2,R/4,R/4);
k=P->Put[y][x]-1;
if(P->Put[y+1][x ]==k){y++;continue;}
if(P->Put[y-1][x ]==k){y--;continue;}
if(P->Put[y ][x+1]==k){x++;continue;}
if(P->Put[y ][x-1]==k){x--;continue;}
}
fillellipse(SX+x*R-R/2,SY+y*R-R/2,R/4,R/4);
}
ПРИЛОЖЕНИЕ Г
П.1. Назначение программы
Программа “Поиск кратчайшего пути” предназначена для нахождения кратчайшего пути в лабиринте. Программа предназначена для использования в учебных заведениях, в познавательных целях. Также возможно использование в целях самопроверки.
П.2. Условия эксплуатации программы
Для того, чтобы работать с данной программой вам необходимо иметь персональный компьютер (минимум 486) с 8 МБ ОЗУ и конечно операционную систему Windows 9x.
П.3. Выполнение программы
Порядок действий, обеспечивающий запуск программы :
- загрузить операционную систему Microsoft Windows9x
- если Вам не удалось загрузить операционную систему Microsoft
Windows 9x или у Вас нет операционной системы Microsoft Windows 9x,
то обратитесь в отдел технической поддержки корпорации Microsoft для
получения соответствующих инструкций. (Электронный адрес отдела
технической поддержки:
megabug_company_tech_department@microsoft.com)
- запустить на выполнение файл sapr_kyrsovik.exe из директории, в которой он расположен.
- После запуска программы на экране монитора можно ознакомиться с управлением программы.
- Клавишами управления следует расставить двери и комнаты в лабиринте, после чего ввести вход и выход из лабиринта.
- подождать пока программа выдаст результат и выйти из программы или начать создание нового лабиринта.
- Для того, чтобы завершить работу с программой необходимо нажать <esc> в любой момент выполнения программы.