UVa 11405 - Can U Win?

// UVa 11405 - Can U Win?

#include <iostream>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;

int move[8][2] = { { 2, 1 }, { 2, -1 }, { -2, 1 }, { -2, -1 }, { 1, 2 }, { 1, -2 }, { -1, 2 }, { -1, -2 } };

struct state {
	int bits;
	int end;
};

bool legal(char ch) {
	return ch == '.' || ch == 'P' || ch == 'k';
}

int main() {
	int cases;
	for (cin >> cases; cases; cases--) {
		// read
		int m;
		cin >> m;
		string board[8];
		getline(cin, board[0]);
		for (int i = 0; i < 8; i++)
			getline(cin, board[i]);
		// build edges
		int cost[64][64];
		memset(cost, 127, sizeof(cost));
		int oo = cost[0][0];
		for (int i = 0; i < 8; i++)
			for (int j = 0; j < 8; j++)
				if (legal(board[i][j])) {
					for (int k = 0; k < 8; k++) {
						int a = i + move[k][0];
						int b = j + move[k][1];
						if (a >= 0 && a < 8 && b >= 0 && b < 8 && legal(board[a][b])) {
							cost[a * 8 + b][i * 8 + j] = 1;
							cost[i * 8 + j][a * 8 + b] = 1;
						}
					}
				}
		// Floyd's
		for (int k = 0; k < 64; k++)
			for (int i = 0; i < 64; i++)
				if (cost[i][k] != oo)
					for (int j = 0; j < 64; j++)
						if (cost[k][j] != oo && cost[i][j] > cost[i][k] + cost[k][j]) {
							cost[i][j] = cost[i][k] + cost[k][j];
						}
		// get pawns
		int knight = 0;
		vector<int> pawn;
		for (int i = 0; i < 8; i++)
			for (int j = 0; j < 8; j++)
				if (board[i][j] == 'P')
					pawn.push_back(i * 8 + j);
				else if (board[i][j] == 'k')
					knight = i * 8 + j;
		// base cases
		int T[256][8], p = pawn.size();
		memset(T, 127, sizeof(T));
		queue<state> q;
		for (int i = 0; i < p; i++)
			if (cost[knight][pawn[i]] != oo) {
				int bits = 1 << i;
				T[bits][i] = cost[knight][pawn[i]];
				q.push( { bits, i });
			}
		// DP
		while (!q.empty()) {
			state f = q.front();
			q.pop();
			for (int i = 0; i < p; i++)
				if (((f.bits >> i) & 1) == 0 && cost[pawn[f.end]][pawn[i]] != oo) {
					int new_bits = f.bits | (1 << i);
					if (T[new_bits][i] == oo) {
						T[new_bits][i] = T[f.bits][f.end] + cost[pawn[f.end]][pawn[i]];
						q.push( { new_bits, i });
					} else if (T[new_bits][i] > T[f.bits][f.end] + cost[pawn[f.end]][pawn[i]])
						T[new_bits][i] = T[f.bits][f.end] + cost[pawn[f.end]][pawn[i]];
				}
		}
		// output
		int sol = oo;
		for (int i = 0; i < p; i++)
			if (T[(1 << p) - 1][i] < sol)
				sol = T[(1 << p) - 1][i];
		if (sol <= m || p == 0)
			cout << "Yes" << endl;
		else
			cout << "No" << endl;
	}
	return 0;
}