Programozás‎ > ‎Feladatok‎ > ‎Kisvakond kalandjai‎ > ‎Megoldás‎ > ‎

og_kisvakondB.cpp

Letöltés: og_kisvakondB.cpp

#include <stdio.h>
#include <iostream>
#include <math.h>

using namespace std;

struct koord
{
    int x;
    int y;
};

struct haz
{
    koord e;
    koord v;
    int es;
    int* el;
    int ut;
};

void beolvas(char*);
bool mehet(haz,haz);
void atir();

int m,t,n;

koord s,c;
haz* hazak;

int main()
{
    beolvas("vakond.txt");
    atir();
    int* q;
    q = new int[n+3];
    q[0]=0;
    hazak[0].ut=0;
    int qs=0;
    int qc=1;
    bool found=false;
    while((!found) && (qs!=qc))
    {
      //  cout << "Haz: "<< q[qs]<< " Ut eddig:" << hazak[q[qs]].ut << "\n";
        for(int i=0; i<hazak[q[qs]].es; i++)
        {
            if(mehet(hazak[q[qs]],hazak[hazak[q[qs]].el[i]]))
            {
                if(hazak[hazak[q[qs]].el[i]].ut==-1)
                {
                    hazak[hazak[q[qs]].el[i]].ut=hazak[q[qs]].ut+1;
                    q[qc]=hazak[q[qs]].el[i];
                    qc++;
                    if(hazak[q[qs]].el[i]==n+1) {found=true;}
                }
            }
        }
        qs++;
    }
    cout << hazak[n+1].ut;
  //  cout << "TEst: " << mehet(hazak[0],hazak[1]);
}

void beolvas(char* file)
{
    FILE* be = fopen(file,"r");
    fscanf(be,"%d",&m);
    fscanf(be,"%d",&t);

    fscanf(be,"%d",&s.x);
    fscanf(be,"%d",&s.y);
    fscanf(be,"%d",&c.x);
    fscanf(be,"%d",&c.y);

    fscanf(be,"%d",&n);

    hazak= new haz[n+3];
    hazak[0].e.x=s.x;
    hazak[0].e.y=s.y;
    hazak[0].v.x=s.x;
    hazak[0].v.y=s.y;

    for(int i=1; i<n+1; i++)
    {
        fscanf(be,"%d",&hazak[i].e.x);
        fscanf(be,"%d",&hazak[i].e.y);
        fscanf(be,"%d",&hazak[i].v.x);
        fscanf(be,"%d",&hazak[i].v.y);
    }
    hazak[n+1].e.x=c.x;
    hazak[n+1].e.y=c.y;
    hazak[n+1].v.x=c.x;
    hazak[n+1].v.y=c.y;

    fclose(be);
}


bool mehet(haz a, haz b)
{
    int x,y,xt,yt;
    xt=a.e.x;
    yt=a.e.y;
    x=b.e.x;
    y=b.e.y;
    float min=sqrt((xt-x)*(xt-x)+(yt-y)*(yt-y));
    bool amig=true;
    float tav;
    while(amig)
    {
        amig=false;
        if(x!=b.v.x)
        {
            x++;
            tav=sqrt((xt-x)*(xt-x)+(yt-y)*(yt-y));
            if(tav<min) {min=tav; x++; amig=true;}
            x--;
        }

        if(y!=b.v.y)
        {
            y++;
            tav=sqrt((xt-x)*(xt-x)+(yt-y)*(yt-y));
            if(tav<min) {min=tav; y++; amig=true;}
            y--;
        }

        if(x!=b.e.x)
        {
            x--;
            tav=sqrt((xt-x)*(xt-x)+(yt-y)*(yt-y));
            if(tav<min) {min=tav; x--; amig=true;}
            x++;
        }

        if(y!=b.e.y)
        {
            y--;
            tav=sqrt((xt-x)*(xt-x)+(yt-y)*(yt-y));
            if(tav<min) {min=tav; y--; amig=true;}
            y++;
        }
    }

    int x2,y2;
    x2=xt;
    y2=yt;

    xt=x;
    yt=y;

    x=x2;
    y=y2;
    min=sqrt((xt-x)*(xt-x)+(yt-y)*(yt-y));
    amig=true;
    while(amig)
    {
        amig=false;
        if(x!=a.v.x)
        {
            x++;
            tav=sqrt((xt-x)*(xt-x)+(yt-y)*(yt-y));
            if(tav<min) {min=tav; x++; amig=true;}
            x--;
        }

        if(y!=a.v.y)
        {
            y++;
            tav=sqrt((xt-x)*(xt-x)+(yt-y)*(yt-y));
            if(tav<min) {min=tav; y++; amig=true;}
            y--;
        }

        if(x!=a.e.x)
        {
            x--;
            tav=sqrt((xt-x)*(xt-x)+(yt-y)*(yt-y));
            if(tav<min) {min=tav; x--; amig=true;}
            x++;
        }

        if(y!=a.e.y)
        {
            y--;
            tav=sqrt((xt-x)*(xt-x)+(yt-y)*(yt-y));
            if(tav<min) {min=tav; y--; amig=true;}
            y++;
        }
    }
    return (t>=(sqrt((xt-x)*(xt-x)+(yt-y)*(yt-y))));
}

void atir()
{
    for(int i=0; i<n+2; i++)
    {
        hazak[i].ut=-1;
        hazak[i].es=0;
        hazak[i].el= new int[n];
        for(int j=0; j<n+2; j++)
        {
            if(i!=j)
            {
                //cout << "Doing" << i << " " << j << " ";
                if(mehet(hazak[i],hazak[j])) {hazak[i].el[hazak[i].es]=j; hazak[i].es++;/* cout << "true\n";*/}
                //else {cout << "false\n";}
            }
        }
    }
}