VPF::[C++] Лабиринт - Форум программистов

Somes

Дата 19.5.2008, 21:33 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 2
Регистрация: 19.5.2008

Репутация: нет
Всего: нет

Задание:
Создать программу, отыскивающую проход по лабиринту.
Лабиринт представляется в виде матрицы, состоящей из квадратов. Каждый квадрат либо открыт, либо закрыт. Вход в закрытый квадрат запрещен. Если квадрат открыт, то вход в него возможет со стороны, но не с угла. Каждый квадрат определяется определяется его координатами в матрице.
Программа находит проход через лабиринт, двигаясь от заданного входа. После отыскания прохода программа выводит найденный путь в виде координат квадратов. Для хранения пути использовать стек.

Код


#include <string.h>
#include <stdio.h>
#include <termios.h>
#include <unistd.h>


////реализация getch
int getch() 
{
struct termios oldt,
newt;
int ch;
tcgetattr( STDIN_FILENO, &oldt );
newt = oldt;
newt.c_lflag &= ~( ICANON | ECHO );
tcsetattr( STDIN_FILENO, TCSANOW, &newt );
ch = getchar();
tcsetattr( STDIN_FILENO, TCSANOW, &oldt );
return ch;
}

struct screen_point{    //
 unsigned char chr;    //
 unsigned char attr;    // Это все нужно для вывода
};      // на экpан.
typedef struct screen_point screen_line[80]; //
screen_line * scr;    //
char movecost[10][10]={
   {0,0,0,0,0,0,0,0,0,0},
   {0,1,6,6,6,6,6,1,1,0},
   {0,1,0,0,0,0,6,0,0,0},
   {0,1,0,1,1,1,1,1,1,0},
   {0,1,0,1,1,0,0,0,1,0}, // Это и есть лабиpинт
   {0,1,0,1,0,0,1,0,1,0}, // 0 - стена
   {0,1,0,1,0,1,1,0,1,0}, // любое дpугое число-
   {0,1,0,0,0,0,0,0,1,0}, //  степень пpоходимости
   {0,1,8,1,1,1,1,1,1,0}, //  1- лучшая пpоходимость
   {0.0,0,0,0,0,0,0,0,0}
                      };
unsigned char fillmap[10][10];  // Pазмеp == pазмеpу лабиpинта !
     // если путь может быть длиннее
     // 255 надо заменить byte->word
struct{
 signed char x,y;  // Кооpдинаты в лабиpинте
}buf[256];   // Чем больше лабиpинт, тем больше должен
    // быть этот массив
unsigned char bufp,bufe; // Индесксы в buf

int sx,sy,tx,ty;  // Hачальные и конечные кооpдинаты пути

/*
  ЭТА ЧАСТЬ ЗАHИМАЕТСЯ ВЫВОДОМ HА ЭКPАH И
                HЕ ИМЕЕТ HИКАКОГО ОТHОШЕHИЯ К АЛГОPИТМУ
*/
void clrscr(){  // Очистить экpан
 int i;
 for(i=0;i<80*25;i++)((short*)scr)[i]=0x0720;
}

// Hапечатать стpоку str в кооpдинатах (x,y) цветом attr
void writestr(int x,int y,char str[],char attr){
int i;
for(i=0;str[i]!=0;i++,x++){scr[y][x].chr=str[i];scr[y][x].attr=attr;}
}

// Pмсует начальную каpтинку лабиpинта
void draw_maze(){
 int i,j;
 for(j=0;j<10;j++)for(i=0;i<10;i++){
  scr[j][i*2  ].attr=16*(7-movecost[j][i])+7+8*((i+j)&1);
  scr[j][i*2+1].attr=16*(7-movecost[j][i])+7+8*((i+j)&1);
 }
 scr[sy][sx*2].chr='[';scr[sy][sx*2+1].chr=']';
 scr[ty][tx*2].chr='<';scr[ty][tx*2+1].chr='>';
 scr[1][40].attr=16*(7-1);writestr(45,1,"Пустое место",7);
 scr[3][40].attr=16*(7-0);writestr(45,3,"Стена",7);
 scr[5][40].attr=16*(7-6);writestr(45,5,"Болото",7);
 writestr(40,7,"[]    Hачальная точка",7);
 writestr(40,9,"<>    Цель пути",7);
}

/*
  А ВОТ ДАЛЬШЕ УЖЕ ИДЕТ PЕАЛИЗАЦИЯ АЛГОPИТМА
*/

/* Эта функция пpовеpяет является ли пpедлогаемый путь в точку более
   коpотким,
   чем найденый pанее, и если да, то запоминает точку в buf.      */
void push(int x,int y,int n){
 if(fillmap[y][x]<=n)return; // Если новый путь не коpоче-нафиг его
 fillmap[y][x]=n;   // Запоминаем новую длину пути
 buf[bufe].x=x;    //
 buf[bufe].y=y;    // Запоминаем точку
 bufe++;   // Pазмеp buf-256 bufe - byte, зациклится само,
    // иначе надо писать bufe=(bufe+1)%(pазмеp buf)
 scr[y][x*2  ].chr=n/10+48;     //
 //Это пpосто pисование и ожидание нажатия кнопки
 scr[y][x*2+1].chr=(n%10)+48;
 getch();   //
}
/* Сдесь беpется очеpедная точка из buf и возвpащается 1, 
  если бpать нечего, то возвpащается 0           */
int pop(int *x,int *y){
 if(bufp==bufe)return 0;
 *x=buf[bufp].x;
 *y=buf[bufp].y;
 bufp++;   // То же, что и с bufe !!!  см. ^
 return 1;
}
/* ВHИМАHИЕ !!! Hе смотpя на названия функций (push и pop) 
   buf это не stack ! Это кольцевой FIFO-шный буфеp !    */

/* Вот, она самая, она-то путь и ищет          */

void fill(int sx,int sy,int tx,int ty){
 int x,y,n,t;
 // Вначале fillmap заполняется max значением
 _fmemset(fillmap,0xFF,sizeof(fillmap)); 
 bufp=bufe=0;    // Думаю понятно...
 push(sx,sy,0);    // Путь в начальную точку =0, логично ?
 while(pop(&x,&y)){   // Цикл, пока есть точки в буфеpе
  if((x==tx)&&(y==ty)){
   writestr(0,20,"Hайден путь длиной     ",15);
   scr[20][19].chr=n/10+48;
   scr[20][20].chr=(n%10)+48;
//   break;// Если pаскоментаpить этот break, то цикл вывалится
   // как только найдется 1-ый же путь. Это логично
   // сделать, если поpходимость всех клеток одинакова.
  }
  // n=длина пути до любой соседней клетки
  n=fillmap[y][x]+movecost[y][x];
  //Пеpебоp 4-х соседних клеток
  if(movecost[y+1][x  ])push(x  ,y+1,n); //
  if(movecost[y-1][x  ])push(x  ,y-1,n); // 
  if(movecost[y  ][x+1])push(x+1,y  ,n); //
  if(movecost[y  ][x-1])push(x-1,y  ,n); //
 }

 // Либо мы нашли 1-ый путь и вывалились по break-у,
 // либо залили уже всю каpту

 if(fillmap[ty][tx]==0xFF){
  writestr(0,20,"Пути не существует !!!",15);
  return;
 }  else 
 writestr(0,20,"Заливка закончена, пpойдемся по пути !!!",15);

 x=tx;y=ty;n=0xFF;    // Мы начали заливку из (sx,sy), значит
     // по пути пpидется идти из (tx,ty)
 while((x!=sx)||(y!=sy)){  // Пока не пpидем в (sx,sy)
  scr[y][x*2].attr=2*16;scr[y][x*2+1].attr=2*16;  // Pисование
  // Сдесь ищется соседняя
  if(fillmap[y+1][x  ]<n){tx=x  ;ty=y+1;t=fillmap[y+1][x  ];} 
  // клетка, содеpжащая
  if(fillmap[y-1][x  ]<n){tx=x  ;ty=y-1;t=fillmap[y-1][x  ];} 
   // минимальное значение
  if(fillmap[y  ][x+1]<n){tx=x+1;ty=y  ;t=fillmap[y  ][x+1];}
  if(fillmap[y  ][x-1]<n){tx=x-1;ty=y  ;t=fillmap[y  ][x-1];}
  x=tx;y=ty;n=t;   // Пеpеходим в найденую клетку

  getch();   // Ждем нажатия кнопки
 }
 // Вот и все ! Путь найден !
}

void main(){
 int i;
 sx=1;sy=1;   // Hачальная точка
 tx=3;ty=3;  // Цель пути

 scr=(screen_line*)0xB8000; //
 clrscr();      // Это все pисование
 draw_maze();    //
 getch();    //

 fill(sx,sy,tx,ty); // Hайдем путь

}

Код взят с сайта про алгоритмы
при компиляции

Код


~ $  g++ -o kurs kursovaya.cpp
kursovaya.cpp:193:2: warning: no newline at end of file
kursovaya.cpp:54: предупреждение: converting to ‘char’ from ‘double’
kursovaya.cpp:60: предупреждение: non-local variable ‘<anonymous struct> buf [256]’ uses anonymous type
kursovaya.cpp: In function ‘void fill(int, int, int, int)’:
kursovaya.cpp:133: ошибка: нет декларации ‘_fmemset’ в этой области видимости
kursovaya.cpp: At global scope:
kursovaya.cpp:181: ошибка: ‘::main’ must return ‘int’
 ~ $

в этом коде мне не всё понятно. подскажите с чем связана ошибка?
еще не могли бы предложить свой вариант кода (наверное более простой) и подходящий под задание?

Это сообщение отредактировал(а) Somes - 19.5.2008, 21:50

t_gran

Дата 20.5.2008, 03:07 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 621
Регистрация: 13.11.2007
Где: г.Усть-Илимск

Репутация: 33
Всего: 37

Ну начнём с того, что это C-ый, а не C++-ый код. Поэтому

Код


$ gcc -o kurs kursovaya.c

Второе, что бросилось в глаза функции _fmemset () нет, это функция из TurboC. Для gcc есть функция memset ().
Втретьих, функция main, в gcc, всегда должна вернуть значение.

По части кода:
Он жестко привязан к TurboC, тебе необходимо выдернуть алгоритм и портировать его на другую платформу.

Это сообщение отредактировал(а) t_gran - 20.5.2008, 08:02

--------------------

Я знаю, что ничего не знаю© Сократ
user posted image

Paulskit

Дата 20.5.2008, 21:45 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 13
Регистрация: 25.11.2007

Репутация: нет
Всего: нет

Я искал недавно тоже как найти кратчайший путь. Глянул - в принципе тебе может подойти тот-же алгоритм (ну конечно переделать не на построение а на хранение координат в стеке - что впрочем я не думаю что будет очень сложной задачей)
В общем вот, сначала забиваем длинами все проходимые (и достижимые клетки)

Код


void move()
{
    int u=0;            //индекс волны
    bool flag=true;        //прошла/не прошла волна
    while (flag) 
    {
        flag=false;
        for (int i=0;i<k;i++)
            for (int j=0;j<k;j++)
                if (s[i][j]==u) 
                {
                    //Проверка соседних клеток на проходимость
                    if ( (s[i-1][j]==127)&&(i>=1) )        { s[i-1][j]=u+1; flag=true; }
                    if ( (s[i+1][j]==127)&&(i+1<k) )    { s[i+1][j]=u+1; flag=true; }
                    if ( (s[i][j-1]==127)&&(j>=1) )        { s[i][j-1]=u+1; flag=true; }
                    if ( (s[i][j+1]==127)&&(j+1<k) )    { s[i][j+1]=u+1; flag=true; }
                }
        u++;    
    }
}

Точка начало - "0", пустая (проходимая) область - "127", k - размер кв. матрицы, s - моя матрица

Далее ищем кратчайший путь (в этом варианте кода - я меняю клетку на 'x' - тебе же сохранять координаты)

Код


void build()
{
    int u=130; 
    int k1=c1,k2=c2;      //координати міста-призначення
    //знаходимо найменше значення біля міста-призначення
    if ( (s[c1-1][c2]<u)&&(c1>=1) )        u=s[c1-1][c2];
    if ( (s[c1+1][c2]<u)&&(c1+1<k) )    u=s[c1+1][c2];
    if ( (s[c1][c2-1]<u)&&(c2>=1) )        u=s[c1][c2-1];
    if ( (s[c1][c2+1]<u)&&(c2+1<k) )    u=s[c1][c2+1];
    if (u>36) cout<<"Дойти до міста "<<s2<<" не можливо не заходячи до інших міст"<<endl;
        else 
        {
            //будуемо шлях (120-'x')
            cout<<"Мінімальний шлях - "<<u<<" кроки(ів)"<<endl;
            while (u!=0)
            {
                if ( (s[k1-1][k2]==u)&&(k1>=1) )    { s[--k1][k2]=120; u--; continue; }
                if ( (s[k1+1][k2]==u)&&(k1+1<k) )    { s[++k1][k2]=120; u--; continue; }
                if ( (s[k1][k2-1]==u)&&(k2>=1) )    { s[k1][--k2]=120; u--; continue; }
                if ( (s[k1][k2+1]==u)&&(k2+1<k) )    { s[k1][++k2]=120; u--; continue; }
            }
        }    
}
З.Ы. Походу должен работать и без continue (в цикле while) - я не проверял.

Это сообщение отредактировал(а) Paulskit - 20.5.2008, 21:46

Andersen1313

Дата 19.10.2010, 16:32 (ссылка)

(голосов:2)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 2
Регистрация: 18.10.2010

Репутация: нет
Всего: нет

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »