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