Veri yapıları ve algoritmalar II – 2.ödev

Ödevi yapmak zorunlu değildir. Son teslim tarihi 25 Ekim Cumartesi 23:59’dur. Ödev kodunu ve ekran çıktısını ödev gönder sayfasından gönderebilirsiniz. Ödevi yalnızca ilk gönderen öğrenci puan alacaktır.

Ödev konusu

Aşağıdaki kod; yığın veri yapısı kullanarak labirentten kaçış algoritması için gerekli fonksiyonları içermektedir. Program bu haliyle maze[][] adlı bir matrisi labirent olarak oluşturmaktadır.

• maze[ ][ ] matrisi labirentOlustur() fonksiyonu ile rasgele oluşturulmaktadır.
• maze[ ][ ] matrisinde değeri 0 olan hücreler yol, 1 olan hücreler duvar ifade eder.
• maze[ ][ ] matrisinin 1,0 (yani 1.satır 0.sütun) hücresi labirentin girişi, 5,6 (yani 5.satır 6.sütun) labirentin çıkışıdır

Koddaki rotaBul() fonksiyonundaki ilgili alan kodlanarak yığın yapısı ile labirentten çıkış rotası oluşturulacaktır. Rota maksimum 20 hücreden geçmelidir. Rotanın geçtiği hücreler rota_x[] ve rota_y[] matrisine yazılacaktır.

#include <iostream>
#include <stdlib.h>
#include <math.h>
#include <locale.h>
using namespace std;


// YIGIN YAPISI KODLARI --------------------------------------------
struct stackYapisi{
    int boyut;
    int *x_index; // Satır indeksini tutacak
    int *y_index; // Sütun indeksini tutacak
    int ust;
};

stackYapisi* createStackYapisi(int boyut)
{
    stackYapisi *yigin = new stackYapisi;
    yigin->boyut = boyut;
    yigin->ust = -1;
    yigin->x_index = new int[boyut];
    yigin->y_index = new int[boyut];
    return yigin;
}

bool isEmpty(stackYapisi &yigin)
{
    if (yigin.ust == -1)
        return true;
    else
        return false;
}

bool isFull(stackYapisi &yigin)
{
    if (yigin.ust == yigin.boyut-1)
        return true;
    else
        return false;
}

bool push(stackYapisi &yigin, int x_index_no, int y_index_no)
{
    if (isFull(yigin) == false)
    {
        yigin.x_index[++yigin.ust] = x_index_no;
        yigin.y_index[++yigin.ust] = y_index_no;
        return true;
    }
    cout<<"Yýðýn dolu";
    return false;
}

bool pop(stackYapisi &yigin)
{
    if (isEmpty(yigin) == false)
    {
        
        yigin.x_index[yigin.ust--] = NULL;
        yigin.y_index[yigin.ust--] = NULL;
        return true;
    }
    return false;
}

void peek(stackYapisi &yigin)
{
    cout<<"En üst eleman: "<<yigin.x_index[yigin.ust]<<","<<yigin.y_index[yigin.ust]<<endl;
}

void display(stackYapisi  &yigin)
{
    if (isEmpty(yigin) == false)
    {
        for (int i = 0; i<=yigin.ust; i++)
            cout<<yigin.x_index[i]<<","<<yigin.y_index[i]<<endl;
    }
    else cout<<"Yýðýn boþ";
}

// LABIRENT KODLARI------------------------------------------------------------------------
// Labirenti oluşturmak için değişkenler
const int en = 5; // Labirentin eni
const int boy = 5; // Labirentin boyu
int maze[en+2][boy+2]; // Labirentin çerçevesini de ekleyerek oluştur
int rota_x[20]; // Çıkışa gidilecek rotanın x indeksleri (satır numaraları)
int rota_y[20]; // Çıkışa gidilecek rotanın y indeksleri (sütun numaraları)

// Labirent oluşturma fonksiyonu
void labirentOlustur(){
    int i;int j;
    // Labirenti oluştur
    srand(unsigned(time(NULL)));
    for (i=0;i<en+2;i++)
        for(j=0;j<en+2;j++)
        {
            if ((i==0)|| (j==0)||(i==en+1)||(j==en+1))
                maze[i][j]=1;
            else{
                maze[i][j] = round(float((rand() % 70))/100); // Yol oluşturma olasılığı %70
            }
        }
    // Labirent giriş ve çıkışlarını oluştur
    maze[1][0] = 0;maze[1][1] = 0; // Sol üst giriş
    maze[en][boy] = 0; maze[en][boy+1] = 0; // sağ alt çıkış
}

// Labirenti ekrana çiz
void labirentYazdir(){
    int i;int j;
    for (i=0;i<en+2;i++){
        for(j=0;j<en+2;j++)
        {
            if (maze[i][j]==0) cout<<" . ";
            else cout<<" # ";
        }
        cout<<endl;
    }
}

// Çıkış rotasını bul
void rotaBul(){
    int i;
    // Rotayı temizle
    for (i=0; i<20;i++){
        rota_x[i] = -1; // -1 olduğunda rota bitti demektir
        rota_y[i] = -1; // -1 olduğunda rota bitti demektir
    }
    // Rotanın ilk elemanı, yani başlangıç noktası 1,0 (1.satır, 0.sütun)
    rota_x[0] = 1;
    rota_y[0] = 0;
    
    /*-------------------ÖDEV--------------------
     -------------------BURAYA--------------------
     -----------------YAZILACAK-------------------*/
}

// Hesaplanan çıkış rotasını yazdır
void rotaYazdir(){
    int i = 0;
    while (rota_x[i]!= -1){ // Rota bitmediği sürece yazdır
        cout<<i+1<<".hücre: "<<rota_x[i]<<","<<rota_y[i]<<endl;
        i++;
    }
}

int main() {
    setlocale(LC_ALL, "Turkish"); // Türkçe karakterleri destekle
    labirentOlustur();
    labirentYazdir();
    rotaBul();
    rotaYazdir();
}