#include<iostream>
#include<vector>
#include<queue>

using namespace std;

class Cell{
    int x;
    int y;
public:
    int getx(){return x;}
    int gety(){return y;}
    void setx(int x){this->x=x;}
    void sety(int y){this->y=y;}

    bool operator==(Cell o){return x==o.x && y==o.y;}
    Cell operator=(Cell o){x=o.x; y=o.y; return *this;}

    Cell(int x,int y):x(x),y(y){}
    Cell():x(0),y(0){}
};
vector<Cell> getShortestPath(Cell ori, Cell dest, int array[], int width, int height);



int main(){
    int ejemplo[]={
        0,1,0,1,0,0,0,0,        //0: void
        0,1,0,1,0,0,0,0,        //1: obstacle
        0,1,0,1,0,0,0,0,
        0,1,0,1,0,0,0,0,
        0,1,0,1,0,0,0,0,
        0,1,0,1,0,0,0,0,
        0,0,0,1,0,0,0,0,
        0,0,0,0,0,0,0,0};

    vector<Cell> camino= getShortestPath(Cell(0,0),Cell(7,0),ejemplo,8,8);
    for(int i=0;i<camino.size();i++){
        cout<<"("<<camino[i].getx()<<", "<<camino[i].gety()<<")"<<endl;
    }

}

vector<Cell> getShortestPath(Cell ori, Cell dest, int array[], int width, int height){

    if(ori==dest) return vector<Cell>();
    unsigned int *sizes=new unsigned int[width*height];
    Cell *prev=new Cell[width*height];
    for(int i=0;i<width*height;i++){sizes[i]=-1; prev[i]=Cell(-1,-1);}

    sizes[ori.getx()+ori.gety()*width]=0;
    prev[ori.getx()+ori.gety()*width]=ori;


    queue<Cell> porVisitar;
    porVisitar.push(ori);

    while(!porVisitar.empty()){
        Cell cur=porVisitar.front();
        porVisitar.pop();
        cout<<porVisitar.size()<<endl;
        for(int i=-1;i<2;i++)
        for(int j=-1;j<2;j++)
        if( (cur.getx()+j)>=0 && (cur.getx()+j)<width && (cur.gety()+i)>=0 && (cur.gety()+i)<height &&      //is not out of bounds
            array[(cur.getx()+j)+(cur.gety()+i)*width]==0 &&            //is not an obstable
            sizes[cur.getx()+cur.gety()*width]+1 < sizes[(cur.getx()+j)+(cur.gety()+i)*width]       //there is not a better path
        ){
            sizes[(cur.getx()+j)+(cur.gety()+i)*width]=sizes[cur.getx()+cur.gety()*width]+1;
            prev[(cur.getx()+j)+(cur.gety()+i)*width]=Cell(cur.getx(),cur.gety());
            porVisitar.push(Cell(cur.getx()+j,cur.gety()+i));
        }

    }

    if(prev[dest.getx()+dest.gety()*width]==Cell(-1,-1)) return vector<Cell>();

    Cell pp=dest;
    vector<Cell> res(sizes[dest.getx()+dest.gety()*width]+1);
    for(int i=res.size()-1; !(pp==ori); i--){
        res[i]=pp;
        pp=prev[pp.getx()+pp.gety()*width];
    }

    return res;

}