//Poszukiwanie drogi w labiryncie
//www.algorytm.org

#include <cstdio>
#include <cstring>

const char *MAPA[]={
"##########",
"# #     ##",
"# #  #   #",
"# #   #  #",
"# ### ## #",
"#     #  #",
"# # ###  #",
"# #    # #",
"#    #   #",
"##########"
};

char val[]="0123456789abcdefghijklmnoprstuvwxyz";

void rysuj(char mapa[10][10]){
    for(int y=0; y<10; y++){
        for(int x=0; x<10; x++){
            if(mapa[x][y]<0)
                printf("#");
            if(mapa[x][y]==0)
                printf(" ");
            else
                printf("%c", val[mapa[x][y]]);
        }
        printf("\n");
    }
    printf("\n");
}

bool zaznacz(char mapa[10][10]){
    // Funkcja potrzebuje mapy w której wartość 1 to punkt startowy, -1 to miejsca gdzie nie może iść
    // 0 to wolne pola
    //Wymaga ramki do okoła
    bool zmiana=false;
    int o;
    for(int y=1; y<9; y++){
        for(int x=1; x<9; x++){
            if(mapa[x][y]<0) continue; //jeśli ściana, sprawdź następny
            o=mapa[x][y]; //przed oznaczeniem
            if(mapa[x+1][y]>0) //prawo jeśli nie ma ściany, ale został odwiedzony
            if(mapa[x+1][y]+1<mapa[x][y] || mapa[x][y]==0) //i jeśli z tamtej drogi jest krócej do aktualnej,
                                                            //lub aktualna jest nieodwiedzona
                mapa[x][y]=mapa[x+1][y]+1; //oznacza tutaj odległość poprzedniej+1

            if(mapa[x-1][y]>0) //lewo
            if(mapa[x-1][y]+1<mapa[x][y] || mapa[x][y]==0)
                mapa[x][y]=mapa[x-1][y]+1;

            if(mapa[x][y+1]>0) //dół
            if(mapa[x][y+1]+1<mapa[x][y] || mapa[x][y]==0)
                mapa[x][y]=mapa[x][y+1]+1;

            if(mapa[x][y-1]>0) //góra
            if(mapa[x][y-1]+1<mapa[x][y] || mapa[x][y]==0)
                mapa[x][y]=mapa[x][y-1]+1;

            if(o!=mapa[x][y]) zmiana=true; //jeśli zaszła zmiana, ustawia na true, że była jakaś zmiana i kolejne wykonanie
                                    //może coś jeszcze zmienić
        }
    }
    return zmiana;
}

void wyczysc(char mapa[10][10],  int odX, int odY, int doX, int doY){
    //Czyszczenie dróg
    bool droga[10][10]; //przechowuje najkrótszą ścieżkę
    memset(droga, 0, 100); //czyszczenie tablicy
    while(odX!=doX || odY!=doY){ //dopóki nie dojdzie od końca do punktu początkowego
        droga[doX][doY]=true;
        //szukanie po sąsiadach najkrótszych odległości, tzn. mniejszych od aktualnej
        //wcześniejsza funkcja daje pewność, że różnice między odległościami zawsze wynoszą 1
        if(mapa[doX+1][doY]<mapa[doX][doY] && mapa[doX+1][doY]>0){
            doX++; continue;
        }
        if(mapa[doX-1][doY]<mapa[doX][doY] && mapa[doX-1][doY]>0){
            doX--; continue;
        }
        if(mapa[doX][doY+1]<mapa[doX][doY] && mapa[doX][doY+1]>0){
            doY++; continue;
        }
        if(mapa[doX][doY-1]<mapa[doX][doY] && mapa[doX][doY-1]>0){
            doY--; continue;
        }
        return; //jeśli jakimś sposobem nie ma najkrótszej drogi, przerywa
    }
    for(int y=1; y<9; y++){
        for(int x=1; x<9; x++){
            if(!droga[x][y])
                if(mapa[x][y]>0)
                    mapa[x][y]=0; //czyszczenie dłuższych dróg
        }
    }
    mapa[odX][odY]=1; //punkt startowy
}

void szukaj(int odX, int odY, int doX, int doY){
    char mapa[10][10];
    for(int i=0; i<100; i++){ //przepisanie mapy, w tym przypadku trzeba ją obrócić
        if(MAPA[i%10][i/10]=='#') //jeśli ściana
            mapa[i/10][i%10]=-1; //przypisz wartość ujemną
        else
            mapa[i/10][i%10]=0; //puste
    }
    printf("Mapa: \n");
        rysuj(mapa); //mapa bez narysowanych scieżek
    mapa[odX][odY]=1; //punkt startoey
    while(zaznacz(mapa)){ //zaznaczanie na mapie kolejno odwiedzanych pól, dopóki są jakiś zmiany, powtarza
        //rysuj(mapa);
    }
    printf("Odleglosci: \n");
    rysuj(mapa); //rysuje mapę z wyznaczonymi odległościami
    wyczysc(mapa, odX, odY, doX, doY); //pozostawia tylko najkrótszą ścieżkę
    printf("Najkrotsza: \n");
    rysuj(mapa); //rysuje mapę po oczyszczeniu
}

int main(){
    szukaj(1,1, 8,4);
    /*
        ##########
        #S#     ##
        # #  #   #
        # #   #  #
        # ### ##E#
        #     #  #
        # # ###  #
        # #    # #
        #    #   #
        ##########
    */
    return 0;
}