JocDeSah - 85p

#include <bits/stdc++.h>
#define x first
#define y second
#define INF 0x3f3f3f3f

using namespace std;

ifstream fin("jocdesah.in");
ofstream fout("jocdesah.out");

struct heap {
    int lives, distance, lin, col, mask;
    bool operator < (const heap& A) const {
        if(lives != A.lives)
            return lives < A.lives;
        if(distance != A.distance)
            return distance > A.distance;
        if(lin != A.lin)
            return lin > A.lin;
        return col > A.col;
    }
};

const int di[] = {-1, 0, 0, 1},
          dj[] = {0, -1, 1, 0};

inline bool Less(const pair < int , int >& a, const pair < int , int >& b) {
    return a.x < b.x || (a.x == b.x && a.y < b.y);
}

int main() {
    int task, N;
    fin >> task >> N;
    vector < string > a(N + 1);
    for(int i = 1; i <= N; ++i) {
        fin >> a[i];
        a[i] = '0' + a[i];
    }
    vector < pair < int , int > > king;
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= N; ++j)
            if(a[i][j] == 'K')
                king.emplace_back(i, j);
    int ans = 0;
    vector < char > piese{'P', 'C', 'N', 'T'};
    auto inside = [&](int lin, int col) {
        return lin > 0 && col > 0 && lin <= N && col <= N;
    };
    int last_lin = -1, last_col = -1, dist = -1;
    vector < vector < pair < int , int > > > last(N + 1, vector < pair < int , int > >(N + 1));
    for(auto it : king) {
        priority_queue < heap > Q;
        Q.push(heap{16, 1, it.x, it.y, 15});
        vector < vector < bool > > viz(N + 1, vector < bool >(N + 1));
        viz[it.x][it.y] = true;
        vector < vector < pair < int , int > > > from(N + 1, vector < pair < int , int > >(N + 1, make_pair(INF, INF)));
        bool ok = false, flag = true;
        while(!Q.empty() && flag) {
            int lives = Q.top().lives,
                distance = Q.top().distance,
                lin = Q.top().lin,
                col = Q.top().col,
                mask = Q.top().mask;
            Q.pop();
            for(int k = 0; k < 4; ++k) {
                int iv = lin + di[k],
                    jv = col + dj[k];
                if(inside(iv, jv) && !viz[iv][jv] && a[iv][jv] != 'K') {
                    viz[iv][jv] = true;
                    pair < int , int > p = make_pair(lin, col);
                    if(Less(p, from[iv][jv]))
                        from[iv][jv] = p;
                    for(int i = 0; i < 4; ++i)
                        if(a[iv][jv] == piese[i]) {
                            int new_lives = lives,
                                new_mask = mask;
                            if(mask & (1 << i)) {
                                new_mask ^= (1 << i);
                                new_lives -= (1 << i);
                            }
                            Q.push(heap{new_lives, distance + 1, iv, jv, new_mask});
                        }
                    if(a[iv][jv] == 'Q') {
                        if(lives > ans) {
                            ans = lives;
                            dist = distance + 1;
                            last_lin = iv;
                            last_col = jv;
                            ok = true;
                        }
                        flag = false;
                        Q.push(heap{lives, distance + 1, iv, jv, mask});
                    }
                }
            }
        }
        if(ok)
            for(int i = 0; i <= N; ++i)
                for(int j = 0; j <= N; ++j)
                    last[i][j] = from[i][j];
    }
    if(task == 1)
        fout << ans;
    else {
        fout << dist << '\n';
        vector < pair < int , int > > sol;
        while(last_lin != INF && last_col != INF) {
            sol.emplace_back(last_lin, last_col);
            int l = last_lin,
                c = last_col;
            last_lin = last[l][c].x;
            last_col = last[l][c].y;
        }
        reverse(sol.begin(), sol.end());
        for(auto it : sol)
            fout << it.x << ' ' << it.y << '\n';
    }
}