#include #include #include #include using namespace std; int n; int inf = 100000001; int id(int a, int b) { if (a < 0 || a >= n || b < 0 || b >= n) { return inf; } return a * 1000 + b; } pair odzyskaj(int n) { return make_pair(n / 1000, n % 1000); } int ojc[1000007], odw[1000002], ile[1000002]; vector kra[1000007]; string znak[102]; int dirbokx[4] = {0, 1, 0, -1}; int dirboky[4] = {1, 0, -1, 0}; int dirskosx[4] = {1, 1, -1, -1}; int dirskosy[4] = {-1, 1, 1, -1}; int dirskoczekx[8] = {-2, -1, 1, 2, 2, 1, -1, -2}; int dirskoczeky[8] = {1, 2, 2, 1, -1, -2, -2, -1}; void aktu(int n) { //cout << n << "\n"; if (ojc[n] == ojc[ojc[n]]) return; aktu(ojc[n]); ojc[n] = ojc[ojc[n]]; } void unionuj(int id1, int id2) { //cout << id1 << " " << id2 << "u\n"; aktu(id1); aktu(id2); //cout << id1 << " " << id2 << "u\n"; if (ojc[id1] != ojc[id2]) { kra[id1].push_back(id2); kra[id2].push_back(id1); //cout << ojc[id1] << " " << ojc[id2] << "uuu\n"; //cout << ojc[ojc[id1]] << " " << ojc[ojc[id2]] << "uuu\n"; ojc[ojc[id1]] = ojc[id2]; } } int32_t main() { //ios_base::sync_with_stdio(0); //cin.tie(0); char typ; cin >> n >> typ; for (int i = 0; i < n; i++) { cin >> znak[i]; for (int j = 0; j < n; j++) { ojc[id(i, j)] = id(i, j); } } ojc[1000001] = 1000001; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (znak[i][j] == '.') { continue; } if (typ == 'K') { for (int h = 0; h < 4; h++) { int nx = i, ny = j, curid = id(i, j); nx += dirbokx[h]; ny += dirboky[h]; int nid = id(nx, ny); if (nid == inf || znak[nx][ny] == '.') continue; unionuj(nid, curid); } for (int h = 0; h < 4; h++) { int nx = i, ny = j, curid = id(i, j); nx += dirskosx[h]; ny += dirskosy[h]; int nid = id(nx, ny); if (nid == inf || znak[nx][ny] == '.') continue; unionuj(nid, curid); } } if (typ == 'B' || typ == 'Q') { for (int h = 0; h < 4; h++) { int nx = i, ny = j, curid = id(i, j); for (int ile = 0; ile < 100; ile++) { nx += dirskosx[h]; ny += dirskosy[h]; int nid = id(nx, ny); if (nid == inf || znak[nx][ny] == '.') continue; unionuj(nid, curid); } } } //cout << "gulp\n"; if (typ == 'R' || typ == 'Q') { for (int h = 0; h < 4; h++) { int nx = i, ny = j, curid = id(i, j); for (int ile = 0; ile < 100; ile++) { nx += dirbokx[h]; ny += dirboky[h]; int nid = id(nx, ny); if (nid == inf || znak[nx][ny] == '.') continue; //cout << i << " " << j << "\n"; //cout << nx << " " << ny << "\n"; unionuj(nid, curid); } } } //cout << "gh\n"; if (typ == 'N') { for (int h = 0; h < 8; h++) { int nx = i, ny = j, curid = id(i, j); nx += dirskoczekx[h]; ny += dirskoczeky[h]; int nid = id(nx, ny); if (nid == inf || znak[nx][ny] == '.') continue; unionuj(nid, curid); } } } } //cout << "uhu\n"; set > s; int glojc = -1; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (znak[i][j] == '.') { continue; } int lid = id(i, j); aktu(lid); if (glojc == -1) { glojc = ojc[lid]; } else { if (glojc != ojc[lid]) { cout << "NO\n"; return 0; } } ile[lid] = kra[lid].size(); s.insert(make_pair(kra[lid].size(), lid)); } } cout << "YES\n"; while (s.size() > 1) { pair para = *s.begin(); s.erase(para); int lid = para.second; for (int i = 0; i < kra[lid].size(); i++) { int v = kra[lid][i]; if (odw[v] == 1) continue; s.erase(make_pair(ile[v], v)); pair skad = odzyskaj(lid); pair dokad = odzyskaj(v); cout << skad.first+1 << " " << skad.second+1 << " " << dokad.first+1 << " " << dokad.second+1 << "\n"; ile[v]--; s.insert(make_pair(ile[v], v)); } odw[lid] = 1; } } /* 3 Q Q.. ... .QQ 3 Q Q.. ... .Q. 3 N N.N N.. .N. 3 R R.R ... .RR 3 R R.. ... .RR */