#include
#include
using namespace std;
int main() {
// prvo vnesuvame kolku redovi i koloni ke ima lavirintot, a posle gi pisuvame negovite elementi
int redovi, koloni;
cin >> redovi >> koloni;
char lavirint[redovi][koloni];
int poseteno[redovi][koloni];
int pocetok_i, pocetok_j; // indeksot na redot i kolonata na pocetnoto pole
for(int i = 0; i < redovi; i++) {
for(int j = 0; j < koloni; j++) {
cin >> lavirint[i][j];
poseteno[i][j] = 0;
if(lavirint[i][j] == 'P') {
pocetok_i = i;
pocetok_j = j;
}
}
}
queue Q;
Q.push(pocetok_i);
Q.push(pocetok_j);
poseteno[pocetok_i][pocetok_j] = 1;
while(Q.size() > 0) {
int ci = Q.front();
Q.pop();
int cj = Q.front();
Q.pop();
cout << ci << " " << cj << endl;
// prvo treba da proverime dali slucajno sme stignale na kraj
if(lavirint[ci][cj] == 'K') {
cout << "Stignavme do krajot" << endl;
break;
}
// probuvame da se dvizime nagore
if(ci - 1 >= 0 and lavirint[ci - 1][cj] != '#' and poseteno[ci - 1][cj] == 0) {
Q.push(ci - 1);
Q.push(cj);
poseteno[ci - 1][cj] = 1;
}
// probuvame da se dvizime nadole
if(ci + 1 < redovi and lavirint[ci + 1][cj] != '#' and poseteno[ci + 1][cj] == 0) {
Q.push(ci + 1);
Q.push(cj);
poseteno[ci + 1][cj] = 1;
}
//probuvame da se dvizime levo
if(cj - 1 >= 0 and lavirint[ci][cj - 1] != '#' and poseteno[ci][cj - 1] == 0) {
Q.push(ci);
Q.push(cj - 1);
poseteno[ci][cj - 1] = 1;
}
// probuvame da se dvizime desno
if(cj + 1 < koloni and lavirint[ci][cj + 1] != '#' and poseteno[ci][cj + 1] == 0) {
Q.push(ci);
Q.push(cj + 1);
poseteno[ci][cj + 1] = 1;
}
}
return 0;
}
/*
4 5
.....
P#...
.....
#.K..
**/