JocDeSah

#include <fstream>
#include <queue>
#include <vector>
#include <tuple>

using namespace std;
using pi = pair<int, int>;

ifstream cin("jocdesah.in");
ofstream cout("jocdesah.out");

int main()
{
	int c, n, di[] = { -1,0,0,1 }, dj[] = { 0,-1,1,0 };
	cin >> c >> n;
	vector<vector<char>> x(n, vector<char>(n));
	vector<pi> K;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
		{
			cin >> x[i][j];
			if (x[i][j] == 'K')
				K.emplace_back(i, j);
		}
	int hans = -1, minlen = 100000;
	pi queenpoz, kingpoz;
	for (const auto& king:K)
		for (int d = 0, ok = 1; d <= 16 && ok; ++d)
		{
			vector<bool> c(4);
			for (int i = 0; i < 4; ++i)
				if (d & (1 << i))
					c[i] = 1;
			queue<pi> q;
			vector<vector<int>> f(n, vector<int>(n));
			f[king.first][king.second] = 1;
			q.emplace(king);
			while (!q.empty())
			{
				int i, j;
				tie(i, j) = q.front();
				q.pop();
				for (int k = 0; k < 4; ++k)
				{
					int iv = i + di[k], jv = j + dj[k];
					if (iv >= 0 && jv >= 0 && iv < n && jv < n && f[iv][jv] == 0 && !(x[iv][jv] == 'K' || x[iv][jv] == 'P' && !c[0] || x[iv][jv] == 'C' && !c[1] || x[iv][jv] == 'N' && !c[2] || x[iv][jv] == 'T' && !c[3]))
					{
						f[iv][jv] = f[i][j] + 1;
						if (x[iv][jv] == 'Q')
						{
							int hcur = 16 - d;
							if (hcur > hans || (hcur == hans && f[iv][jv] < minlen))
							{
								ok = 0;
								hans = hcur;
								minlen = f[iv][jv];
								kingpoz = king;
								queenpoz = make_pair(iv, jv);
							}
							while (!q.empty())
								q.pop();
							break;
						}
						q.emplace(iv, jv);
					}
				}
			}
		}
	if (c == 2)
	{
		int d = 16 - hans;
		vector<bool> c(4);
		for (int i = 0; i < 4; ++i)
			if (d & (1 << i))
				c[i] = 1;
		vector<vector<int>> f(n, vector<int>(n));
		queue<pi> q;
		q.emplace(queenpoz);
		f[queenpoz.first][queenpoz.second] = 1;
		while (!q.empty())
		{
			int i, j;
			tie(i, j) = q.front();
			q.pop();
			for (int k = 0; k < 4; ++k)
			{
				int iv = i + di[k], jv = j + dj[k];
				if (iv >= 0 && jv >= 0 && iv < n && jv < n && f[iv][jv] == 0 && !(x[iv][jv] == 'Q' || x[iv][jv] == 'P' && !c[0] || x[iv][jv] == 'C' && !c[1] || x[iv][jv] == 'N' && !c[2] || x[iv][jv] == 'T' && !c[3]))
				{
					f[iv][jv] = f[i][j] + 1;
					if (f[iv][jv] < minlen)
						q.emplace(iv, jv);
				}
			}
		}
		cout << minlen << '\n';
		int i, j;
		tie(i, j) = kingpoz;
		cout << 1 + i << ' ' << 1 + j << '\n';
		for (int iv, jv; f[i][j] != 1; i = iv, j = jv, cout << 1 + i << ' ' << 1 + j << '\n')
			for (int k = 0; k < 4; ++k)
			{
				iv = i + di[k], jv = j + dj[k];
				if (iv >= 0 && jv >= 0 && iv < n && jv < n && f[i][j] - 1 == f[i + di[k]][j + dj[k]])
					break;
			}
	}
	else cout << hans;
}