Welcome to Stratos!
#include <iostream>#include <vector>#include <cstdlib>#include <iostream>#include <algorithm> // std::sort#include <stdlib.h>using namespace std;///0 camino, 1 inacesible, heroe se pone a 5./*#define tamX 6//3//6#define tamY 5//3//5#define tileX 1////3#define tileY 2//2//3*//*///mapa1, inici:2-2, fin 2-5///3*4= 8-6, 8-15#define tamX 7//3//6#define tamY 5//3//5#define tileX 3////3#define tileY 4//2//3*//*///mapa2, inici 3-1, fin 1-3///3*4 12-3, 4-9#define tamX 6//3//6#define tamY 5//3//5#define tileX 3////3#define tileY 4//2//3*////mapa3, el completo///i 0-0, 9-11, 3*4= 0,0,, 36-33#define tamX 12//3//6#define tamY 10//3//5#define tileX 3////3#define tileY 4//2//3struct vertice{ int posx;///la posicion que ocupa en la matriz int posy; int valor; int pos=-1;///la posicion que ocupa en la array <0,0>=0; <0,1>1, 0,2=2 etc... vector<int>adjy;/// vector<int>adjx;/// vector<int>adj;///con posiciones direcamtne int g=10; int f=-1; int padrex=-1;///para saber la ruta int padrey=-1; int padre=-1; ///hijo, lo mismo ke el padre pero al reves int hijox=-1; int hijoy=-1; int hijo=-1; bool visitado=false; ///es la 1r posicion de cada celda del grafo " si cada tile ocupa...3 celdas del grafo pues apuntara ///a la 1r celda ke es arriba izkierda int maty; int matx;};struct comparador {///operador para realizar las modificaciones de ordenadcion de mi vector bool operator() (vertice i,vertice j) { return (i.f>j.f);}} mayorF;int mapa[tamY][tamX];///dimensiones del mapa 6x, 5y vertice grafo[tamY*tileY][tamX*tileX];///cada tile del mapa son *10 pixelesvoid llenar();void mapa1();void mapa2();void mapa3();void llenargrafo();void imprimir();void ponerAdj();void saberAdj();void saberpos();void BuscarCamino(int,int,int,int);///meto las posiciones "0,0" de las celdas del grafo de los tiles.void imprimirpos();int main(){ mapa3(); llenargrafo(); ponerAdj(); imprimir(); BuscarCamino(0,0,36,33); imprimir(); return 0;}void BuscarCamino(int iy,int ix, int fy, int fx){ vertice inici=grafo[iy][ix]; vertice fin=grafo[fy][fx]; vector<vertice> cola; ///lo ke hace es... si son 2 pixeles a mirar en x, y 3 en y "el tamaño tile es 2x3 ///pues cuando alla 2 x conb misma posicion entonces metelo sino no... /// i se mete en la cola vector<vertice>vistox; vector<vertice>vistoy; int contx=0; int conty=0; cola.push_back(inici); //back es 1r valor, pop es kitarlo while (cola.size()>0)///mientras hay elementos { vertice v=cola.back(); cola.pop_back(); if(!v.visitado) { vistox.clear(); vistoy.clear(); contx=0; conty=0; grafo[v.maty][v.matx].visitado=true;///se mira el visitado de la 1r casilla if(v.pos!=fin.pos)///sino hemos llegado { for(int y1=v.maty; y1<v.maty+tileY; y1++)///recorremos las celdas ke tiene cada "tile grande" en el grafo { for(int x1=v.matx; x1<v.matx+tileX; x1++) { for(int i=0; i<grafo[y1][x1].adj.size(); i++)///recorremos todos los adj de cada punto { int vy,vx;///guardo las posiciones asi para que no alla tanto lio, ///quiero la 0,0 de cada tile. vy=grafo[y1][x1].adjy[i]; vx=grafo[y1][x1].adjx[i]; int ay,ax; ay=grafo[vy][vx].maty; ax=grafo[vy][vx].matx; vertice vadj=grafo[ay][ax];///adj de cada posicion if(!vadj.visitado and vadj.pos!=v.pos)///si esta visitado pake verlo,ke su adj sea diferente a el mismo { int peso=v.g+(abs(vadj.posy-fin.posy)+abs(vadj.posx-fin.posy)); ///si tiene mismo padre...esque es una continuacion del tile, sumalo! if(peso<vadj.f or vadj.f==-1 or vadj.padre==v.pos)///si el peso es menor o aun no se a iniciado "-1" metelo { if(vadj.padre!=v.pos)///si no son mismo padre az como siemrpre. { vadj.padre=v.pos;///assignamos el padre de los adj como su padre su posicion vadj.padrey=v.posy; vadj.padrex=v.posx; vadj.f=peso; vadj.g=vadj.g+v.g;///se le suma cout<<"padre "<<vadj.padre<<" yo "<<vadj.pos<<endl; } else { vadj.f+=peso;///le sumamos mas el peso, la g se mantiene. } /// cout<< vadj.f<<" vady "<<vadj.posy<<" x "<<vadj.posx<< " finy "<< fin.posy <<" x "<<fin.posx <<endl; grafo[ay][ax]=vadj;///se iwala para ke coja todas las referencias, es pa trbaajr mas comodo if(v.posy!=vadj.posy)///kiere decir ke estmaos mirando adj arriba /abajo { vistoy.push_back(vadj); for(int i=0; i<vistoy.size(); i++) { if(vistoy[i].pos==vadj.pos)///si hay n=tile de los añadidmos, bien se puede ir { conty++; } } if(conty>=tileX)cola.push_back(vadj); conty=0; } else if(v.posx!=vadj.posx)///kiere decir ke estmaos mirando adj arriba /abajo { vistox.push_back(vadj); for(int i=0; i<vistox.size(); i++) { if(vistox[i].pos==vadj.pos)///si hay n=tile de los añadidmos, bien se puede ir { contx++; } } if(contx>=tileY)cola.push_back(vadj); contx=0; } std::sort (cola.begin(), cola.end(), mayorF);///ordenamos la array apra sacar el menor F } } } } } } } }///padre vertice ruta=grafo[1][3]; ruta=grafo[36][33];cout<<"camino "<< ruta.pos<<endl; while (ruta.padrey!=-1)///x o y es lo mismo! { cout<<ruta.pos<<endl; //grafo[ruta.padrey][ruta.padrex].valor=3; grafo[ruta.padrey][ruta.padrex].hijo=ruta.pos; grafo[ruta.padrey][ruta.padrex].hijoy=ruta.posy; grafo[ruta.padrey][ruta.padrex].hijox=ruta.posx; ruta=grafo[ruta.padrey][ruta.padrex]; } ruta=grafo[0][0];cout<<"camino "<< ruta.hijo<<endl; while (ruta.hijo!=-1)///x o y es lo mismo! { cout<<ruta.pos<<endl; for(int y1=ruta.maty; y1<ruta.maty+tileY; y1++)///recorremos las celdas ke tiene cada "tile grande" en el grafo { for(int x1=ruta.matx; x1<ruta.matx+tileX; x1++) { //grafo[ruta.hijoy][ruta.hijox].valor=3; grafo[y1][x1].valor=3; } } ruta=grafo[ruta.hijoy][ruta.hijox]; }}void saberpos(){ for(int y1=0; y1<tamY*tileY; y1++){ for(int x1=0; x1<tamX*tileX; x1++){ cout<<grafo[y1][x1].pos<<" "<<endl; } cout<<endl; }}void ponerAdj(){ for(int y=0; y<tamY; y++){ for(int x=0; x<tamX; x++){ if(mapa[y][x]!=1)///no es pared solida { // cout<<" estat "<<y<<" "<<x<<endl; for(int y1=y*tileY; y1<y*tileY+tileY; y1++){ for(int x1=x*tileX; x1<x*tileX+tileX; x1++){ // cout<<"grafo y-x "<<y1<<" "<<x1<<endl; ///miramos las 4 posiciones para meterlas if(grafo[y1][x1-1].valor!=1 and x1-1>=0)///su izkierda { // cout<<"entra iz "<<x1-1<< "adj a pos "<<grafo[y1][x1-1].pos<<endl; grafo[y1][x1].adj.push_back(grafo[y1][x1-1].pos); grafo[y1][x1].adjy.push_back(y1); grafo[y1][x1].adjx.push_back(x1-1); } if(grafo[y1][x1+1].valor!=1 and x1+1<tamX*tileX)///derecha {//cout<<"entra de "<<x1+1<< "adj a pos "<<grafo[y1][x1+1].pos<<endl; grafo[y1][x1].adj.push_back(grafo[y1][x1+1].pos); grafo[y1][x1].adjy.push_back(y1); grafo[y1][x1].adjx.push_back(x1+1); } if(grafo[y1-1][x1].valor!=1 and y1-1>=0)///arriba {//cout<<"entra arr "<<y1-1<< "adj a pos "<<grafo[y1-1][x1].pos<<endl; grafo[y1][x1].adj.push_back(grafo[y1-1][x1].pos); grafo[y1][x1].adjy.push_back(y1-1); grafo[y1][x1].adjx.push_back(x1); } if(grafo[y1+1][x1].valor!=1 and y1+1<tamY*tileY)///abajo {//cout<<"entra ab "<<y1+1<< "adj a pos "<<grafo[y1+1][x1].pos<<endl; grafo[y1][x1].adj.push_back(grafo[y1+1][x1].pos); grafo[y1][x1].adjy.push_back(y1+1); grafo[y1][x1].adjx.push_back(x1); } } } } } }}void saberAdj(){ for(int y1=0; y1<tamY*tileY; y1++){ for(int x1=0; x1<tamX*tileX; x1++){ for(int i=0; i<grafo[y1][x1].adj.size();i++)cout<<" pos y "<<y1<<" "<<x1 <<" = "<<grafo[y1][x1].adj[i]<<endl; //for(int i=0; i<grafo[y1][x1].adjy.size();i++)cout<<" pos y "<<y1<<" "<<x1 <<" = "<<grafo[y1][x1].adjy[i]<<endl; //for(int i=0; i<grafo[y1][x1].adjx.size();i++)cout<<" pos x "<<y1<<" "<<x1 <<" = "<<grafo[y1][x1].adjx[i]<<endl; } }}void imprimir(){ for(int y=0; y<tamY; y++){ for(int x=0; x<tamX; x++) cout<<mapa[y][x]<<" "; cout<<endl; } cout<<endl; for(int y1=0; y1<tamY*tileY; y1++){ for(int x1=0; x1<tamX*tileX; x1++){ cout<<grafo[y1][x1].valor<<" "; } cout<<endl; }}void imprimirpos(){ cout<<endl; for(int y1=0; y1<tamY*tileY; y1++){ for(int x1=0; x1<tamX*tileX; x1++){ cout<<grafo[y1][x1].pos<<" "; } cout<<endl; }}void llenargrafo(){ int n=0; for(int y=0; y<tamY; y++){ for(int x=0; x<tamX; x++){ for(int y1=y*tileY; y1<y*tileY+tileY; y1++){ for(int x1=x*tileX; x1<x*tileX+tileX; x1++){ grafo[y1][x1].pos=n; grafo[y1][x1].valor=mapa[y][x]; grafo[y1][x1].posx=x1; grafo[y1][x1].posy=y1; grafo[y1][x1].maty=y*tileY; grafo[y1][x1].matx=x*tileX; } } n++; } }}void llenar(){ /* mapa[0][0]=5; mapa[0][1]=0; mapa[0][2]=0; mapa[1][0]=0; mapa[1][1]=1; mapa[1][2]=0; mapa[2][0]=0; mapa[2][1]=1; mapa[2][2]=6; */ /*mapa[0][0]=0; mapa[0][1]=1; mapa[1][0]=0; mapa[1][1]=1; */ mapa[0][0]=5;//5 mapa[0][1]=0; mapa[0][2]=1; mapa[0][3]=1; mapa[0][4]=0; mapa[0][5]=1; mapa[1][0]=1; mapa[1][1]=0; mapa[1][2]=0; mapa[1][3]=0; mapa[1][4]=0; mapa[1][5]=1; mapa[2][0]=0; mapa[2][1]=0; mapa[2][2]=1; mapa[2][3]=1; mapa[2][4]=0; mapa[2][5]=0; mapa[3][0]=0; mapa[3][1]=1;///SSSSSS mapa[3][2]=1; mapa[3][3]=1; mapa[3][4]=1; mapa[3][5]=0; mapa[4][0]=0; mapa[4][1]=0; mapa[4][2]=0; mapa[4][3]=0; mapa[4][4]=6; mapa[4][5]=0;}void mapa1(){ mapa[0][0]=0;//5 mapa[0][1]=0; mapa[0][2]=0; mapa[0][3]=0; mapa[0][4]=0; mapa[0][5]=0; mapa[0][6]=0; mapa[1][0]=0; mapa[1][1]=0; mapa[1][2]=0; mapa[1][3]=1; mapa[1][4]=0; mapa[1][5]=0; mapa[1][6]=0; mapa[2][0]=0; mapa[2][1]=0; mapa[2][2]=5; mapa[2][3]=1; mapa[2][4]=0; mapa[2][5]=6; mapa[2][6]=0; mapa[3][0]=0; mapa[3][1]=0;///SSSSSS mapa[3][2]=0; mapa[3][3]=1; mapa[3][4]=0; mapa[3][5]=0; mapa[3][6]=0; mapa[4][0]=0; mapa[4][1]=0; mapa[4][2]=0; mapa[4][3]=0; mapa[4][4]=0; mapa[4][5]=0; mapa[4][6]=0; mapa[5][0]=0; mapa[5][1]=0; mapa[5][2]=0; mapa[5][3]=0; mapa[5][4]=0; mapa[5][5]=0; mapa[5][6]=0;}void mapa2(){ mapa[0][0]=0;//5 mapa[0][1]=0; mapa[0][2]=0; mapa[0][3]=0; mapa[0][4]=0; mapa[0][5]=0; mapa[1][0]=0; mapa[1][1]=0; mapa[1][2]=0; mapa[1][3]=6; mapa[1][4]=0; mapa[1][5]=0; mapa[2][0]=0; mapa[2][1]=1; mapa[2][2]=1; mapa[2][3]=1; mapa[2][4]=0; mapa[2][5]=0; mapa[3][0]=0; mapa[3][1]=5;///SSSSSS mapa[3][2]=0; mapa[3][3]=1; mapa[3][4]=0; mapa[3][5]=0; mapa[4][0]=0; mapa[4][1]=0; mapa[4][2]=0; mapa[4][3]=0; mapa[4][4]=0; mapa[4][5]=0;}void mapa3(){ mapa[0][0]=5;//5 mapa[0][1]=0; mapa[0][2]=0; mapa[0][3]=0; mapa[0][4]=0; mapa[0][5]=1; mapa[0][6]=1; mapa[0][7]=1; mapa[0][8]=0; mapa[0][9]=0; mapa[0][10]=0; mapa[0][11]=0; mapa[1][0]=1;//5 mapa[1][1]=0; mapa[1][2]=1; mapa[1][3]=1; mapa[1][4]=0; mapa[1][5]=1; mapa[1][6]=0; mapa[1][7]=0; mapa[1][8]=0; mapa[1][9]=1; mapa[1][10]=1; mapa[1][11]=0; mapa[2][0]=1;//5 mapa[2][1]=0; mapa[2][2]=1; mapa[2][3]=0; mapa[2][4]=1; mapa[2][5]=0; mapa[2][6]=0; mapa[2][7]=0; mapa[2][8]=1; mapa[2][9]=1; mapa[2][10]=0; mapa[2][11]=0; mapa[3][0]=1;//5 mapa[3][1]=0; mapa[3][2]=1; mapa[3][3]=0; mapa[3][4]=0; mapa[3][5]=0; mapa[3][6]=1; mapa[3][7]=0; mapa[3][8]=0; mapa[3][9]=1; mapa[3][10]=0; mapa[3][11]=1; mapa[4][0]=0;//5 mapa[4][1]=0; mapa[4][2]=1; mapa[4][3]=1; mapa[4][4]=0; mapa[4][5]=0; mapa[4][6]=1; mapa[4][7]=0; mapa[4][8]=0; mapa[4][9]=1; mapa[4][10]=0; mapa[4][11]=0; mapa[5][0]=0;//5 mapa[5][1]=1; mapa[5][2]=1; mapa[5][3]=0; mapa[5][4]=0; mapa[5][5]=1; mapa[5][6]=1; mapa[5][7]=1; mapa[5][8]=1; mapa[5][9]=0; mapa[5][10]=1; mapa[5][11]=0; mapa[6][0]=0;//5 mapa[6][1]=0; mapa[6][2]=0; mapa[6][3]=0; mapa[6][4]=1; mapa[6][5]=0; mapa[6][6]=0; mapa[6][7]=0; mapa[6][8]=0; mapa[6][9]=0; mapa[6][10]=0; mapa[6][11]=0; mapa[7][0]=0;//5 mapa[7][1]=0; mapa[7][2]=1; mapa[7][3]=0; mapa[7][4]=1; mapa[7][5]=0; mapa[7][6]=1; mapa[7][7]=0; mapa[7][8]=1; mapa[7][9]=1; mapa[7][10]=1; mapa[7][11]=1; mapa[8][0]=1;//5 mapa[8][1]=0; mapa[8][2]=0; mapa[8][3]=0; mapa[8][4]=1; mapa[8][5]=0; mapa[8][6]=0; mapa[8][7]=1; mapa[8][8]=0; mapa[8][9]=0; mapa[8][10]=0; mapa[8][11]=0; mapa[9][0]=1;//5 mapa[9][1]=0; mapa[9][2]=1; mapa[9][3]=0; mapa[9][4]=1; mapa[9][5]=0; mapa[9][6]=0; mapa[9][7]=0; mapa[9][8]=0; mapa[9][9]=0; mapa[9][10]=1; mapa[9][11]=6;}