public:

int K,P;

vector< pii > Ps;

vector< pii > Ks;

int minDis(int k, int s){

queue< pii > Q;

bool visited[11];

memset(visited,0,sizeof(visited));

vector< pii > V;

int cnt = 0;

for(int i=0; i<P; i++){

if(((s>>i)&1) == 1){

V.push_back( Ps[i] );

cnt++;

}

}

int sum = 0;

pii cur(Ks[k].first, Ks[k].second);

int t_cnt = cnt;

while(t_cnt--){

int t_min=INF;

int t_pos;

pii next;

for(int i=0; i<cnt; i++){

if(visited[i]==false){

int t = cur.first-V[i].first + cur.second-V[i].second;

cout<<"t = "<<t<<endl;

if(t<t_min){

t_min = t;

next = V[i];

t_pos = i;

}

}

}

visited[t_pos] = true;

sum+=t_min;

cur = next;

}

return sum;

}

int work(){

for(int i=0; i<(1<<MAXN); i++)dp[i] = INF;

dp[0] = 0;

cout<<"K = "<<K<<" P = "<<P<<endl;

for(int k=0; k<K; k++){

for(int s=(1<<P)-1; s>=0; s--){

if(dp[s]==INF)continue;

for(int to=0; to<(1<<P); to++){

if((s&to)!=s)continue;

int add = (s^to);

int cost = minDis(k, add);

if(to==31){

cout<<"cost = "<<cost<<endl;

}

dp[to] = min(dp[s]+cost, dp[to]);

}

}

}

return dp[ (1<<P)-1];

}

int minNumberOfMoves(vector <string> board) {

Ps.clear();

for(int i=0; i<board.size(); i++){

for(int j=0; j<board[0].size(); j++){

if(board[i][j]=='P'){

P++;

Ps.push_back( pii(i,j) );

}else if(board[i][j]=='K'){

K++;

Ks.push_back( pii(i,j) );

}

}

}

return work();

}

cout << "Test " << testNum << ": [" << "{";

for (int i = 0; int(p0.size()) > i; ++i) {

if (i > 0) {

cout << ",";

}

cout << "\"" << p0[i] << "\"";

}

cout << "}";

cout << "]" << endl;

PawnsAndKings *obj;

int answer;

obj = new PawnsAndKings();

clock_t startTime = clock();

answer = obj->minNumberOfMoves(p0);

clock_t endTime = clock();

delete obj;

bool res;

res = true;

cout << "Time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " seconds" << endl;

if (hasAnswer) {

cout << "Desired answer:" << endl;

cout << "\t" << p1 << endl;

}

cout << "Your answer:" << endl;

cout << "\t" << answer << endl;

if (hasAnswer) {

res = answer == p1;

}

if (!res) {

cout << "DOESN'T MATCH!!!!" << endl;

} else if (double(endTime - startTime) / CLOCKS_PER_SEC >= 2) {

cout << "FAIL the timeout" << endl;

res = false;

} else if (hasAnswer) {

cout << "Match :-)" << endl;

} else {

cout << "OK, but is it right?" << endl;

}

cout << "" << endl;

return res;

bool all_right;

all_right = true;

vector <string> p0;

int p1;

{

// ----- test 0 -----

string t0[] = {".PPPPKP.","........","........","........","........","........","........","........"};

p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));

p1 = 6;

all_right = KawigiEdit_RunTest(0, p0, true, p1) && all_right;

// ------------------

}

return 0;

{

// ----- test 1 -----

string t0[] = {"P......P","........","........","........","...KK...","........","........","P......P"};

p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));

p1 = 20;

all_right = KawigiEdit_RunTest(1, p0, true, p1) && all_right;

// ------------------

}

{

// ----- test 2 -----

string t0[] = {".....P.P","..K....P","....K...","..PP...P","...K..KK","........","K.......","KP.K...."};

p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));

p1 = 9;

all_right = KawigiEdit_RunTest(2, p0, true, p1) && all_right;

// ------------------

}

{

// ----- test 3 -----

string t0[] = {"PK...KPK","......K.","...K....","..KPK...","...K....","........","........","K..P.K.P"};

p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));

p1 = 8;

all_right = KawigiEdit_RunTest(3, p0, true, p1) && all_right;

// ------------------

}

if (all_right) {

cout << "You're a stud (at least on the example cases)!" << endl;

} else {

cout << "Some of the test cases had errors." << endl;

}

return 0;