Cavall

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

using namespace std;

typedef vector<vector<char> > Table;
typedef pair<int,pair<int,int> > info;
typedef priority_queue<info, vector<info>, greater<info> > PQ;

const int X[8] = {1, 1, 2, 2, -1, -1, -2, -2};
const int Y[8] = {2, -2, 1, -1, 2, -2, -1, 1};
const int INFINITE = 1e9;

bool posicio_correcte (int n, int m, int x, int y) {
    return 0 <= x and x < n and 0 <= y and y < m;
}
bool backtracking (const Table& T, pair<int,int> Cav, int& D)
{
    int n = T.size(), m = T[0].size();
    vector<vector<bool> > vis (n, vector<bool> (m, false));
    vector<vector<int> > distancies (n, vector<int> (m,INFINITE));
    distancies[Cav.first][Cav.second] = 0;
    PQ Q;
    Q.push(make_pair(0,Cav));
    while (not Q.empty()) {
        int dist = Q.top().first;
        pair<int,int> Pos = Q.top().second;
        Q.pop();
        //cout << Pos.first << " " << Pos.second << endl;
        if (T[Pos.first][Pos.second] == 'p') {
            D = dist;
            return true;
        }
        if (not vis[Pos.first][Pos.second]) {
            vis[Pos.first][Pos.second] = true;
            for (int i = 0; i < 8; ++i) {
                if (posicio_correcte(n, m, Pos.first + X[i], Pos.second + Y[i])
                    and T[Pos.first + X[i]][Pos.second + Y[i]] != 'X')
                    {
                        //cout << "Ha entrat" << endl;
                        info aux;
                        aux.first = dist + 1;
                        aux.second = make_pair(Pos.first + X[i],Pos.second + Y[i]);
                        if (distancies[aux.second.first][aux.second.second] > aux.first) {
                                distancies[aux.second.first][aux.second.second] = aux.first;
                            Q.push(aux);
                        }
                        else {
                            distancies[aux.second.first][aux.second.second] = aux.first;
                            Q.push(aux);
                        }
                    }
            }
        }
    }
    return false;
}

void read_table (Table& T, int f, int c)
{
    for (int i = 0; i < f; ++i) {
        for (int j = 0; j < c; ++j) {
            cin >> T[i][j];
        }
    }
}
int main () {
    int f, c;
    while (cin >> f >> c) {
        /* f i c estan entre 3 i 200*/
        Table T(f, vector<char> (c));
        read_table(T,f,c);
        pair<int, int> Cav;
        cin >> Cav.first >> Cav.second;
        Cav.first -= 1;
        Cav.second -= 1;
        int dist;
        bool Pot_arribar = backtracking(T, Cav, dist);
        if (Pot_arribar) cout << dist;
        else cout << "no";
        cout << endl;
    }
}