#include <iostream>
#include <fstream>
#include <conio.h>
#include <cstdlib>
#include <windows.h>
using namespace std;

void wczytanie(char tab[1000][1000],int &wys,int &szer)
{
    szer=0,wys=0;


   fstream input("labirynt4.txt",ios::in | ios::binary);

   string wiersz;
   getline(input,wiersz);
   szer = wiersz.length();

   input.seekg(0,input.end);
   wys=input.tellg()/szer;

   input.seekg(0,input.beg);


    cout << "WYS: " << wys << "  SZER: " << szer << endl;

   for(int i=0;i<wys;i++)
   {
        getline(input,wiersz);
        for(int j=0;j<szer;j++)
        {
            tab[i][j]=wiersz[j];
        }
    }

    input.close();


}
void kolorki(int jaki)
{
    SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE),jaki);
}
void wyswietlanie(char tab[1000][1000],int wys,int szer,int licznik_krokow)
{
    system("cls");

    for(int i=0;i<wys;i++)
   {
       for(int j=0;j<szer;j++)
       {

            if(tab[i][j]=='x')
            {
                kolorki(9);
                cout << tab[i][j];
                kolorki(15);
            }

            else if(tab[i][j]=='X')
            {
                kolorki(5);
                cout << "X";
                kolorki(15);
            }
            else if(tab[i][j]=='p')
            {
                kolorki(11);
                cout << "p";
                kolorki(15);
            }
            else if(tab[i][j]=='k')
            {
                kolorki(10);
                cout << "k";
                kolorki(15);
            }
            else
            {
                cout << tab[i][j];
            }
       }
       cout << endl;
   }
   cout << endl;
   cout << "LICZNIK KROKOW:  " << licznik_krokow << endl;
}
void find_p(char tab[1000][1000],int &x,int &y,int wys,int szer)
{
    for(int i=0;i<wys;i++)
   {
        for(int j=0;j<szer;j++)
        {
            if(tab[i][j]=='p')
            {
                x=j;
                y=i;
            }
        }
    }
}
void move_p(char tab[1000][1000],int x,int y,int new_x,int new_y)
{
    tab[y][x]='o';
    tab[new_y][new_x]='p';

}
bool play(char tab[1000][1000],int x,int y,int wys,int szer,int old_x,int old_y,int &licznik_krokow)
{

    //cout << licznik_krokow << endl;
    licznik_krokow++;
    //cout << x << "  " << y << endl;

    if(tab[y][x]=='k')
    {
        cout << "TO KONIEC" << endl;
        return true;
    }
    else if(tab[y][x]=='x' || tab[y][x]=='X')
    {
        tab[y][x]='X';
        return false;
    }
    else
    {
        move_p(tab,old_x,old_y,x,y);
        //wyswietlanie(tab,wys,szer,licznik_krokow);

        //1-w prawo
        if(tab[y][x+1]!='o')
        {
            if(play(tab,x+1,y,wys,szer,x,y,licznik_krokow))
            {
                return true;
            }
        }

        //2-w lewo
        if(tab[y][x-1]!='o')
        {
            if(play(tab,x-1,y,wys,szer,x,y,licznik_krokow))
            {
                return true;
            }
        }

        //3-w dol
        if(tab[y+1][x]!='o')
        {
            if(play(tab,x,y+1,wys,szer,x,y,licznik_krokow))
            {
                return true;
            }
        }

        //4-w gore
        if(tab[y-1][x]!='o')
        {
            if(play(tab,x,y-1,wys,szer,x,y,licznik_krokow))
            {
                return true;
            }
        }


            move_p(tab,x,y,old_x,old_y);
            //wyswietlanie(tab,wys,szer,licznik_krokow);


        return false;
    }



}

int main()
{
    char tab[1000][1000]={""};
    int wys,szer;

    int licznik_krokow=0;

    wczytanie(tab,wys,szer);
    int xk=0,yk=0;
    int x=0,y=0;
    find_p(tab,x,y,wys,szer);
    find_p(tab,xk,yk,wys,szer);
    //cout << xk << "  " << yk << endl;
    play(tab,x,y,wys,szer,1,1,licznik_krokow);
    cout << licznik_krokow << endl;

    return 0;
}