#include using namespace std; using LL = long long; #define FOR(i, l, r) for(int i = (l); i <= (r); ++i) #define REP(i, n) FOR(i, 0, (n) - 1) #define ssize(x) int(x.size()) template auto& operator<<(ostream &o, pair p) { return o << '(' << p.first << ", " << p.second << ')'; } template auto operator<<(ostream &o, T x) -> decltype(x.end(), o) { o << '{'; int i = 0; for(auto e : x) o << (", ")+2*!i++ << e; return o << '}'; } ostream& operator<<(ostream &o, string &s) { return o << s.data(); } #ifdef DEBUG #define debug(x...) cerr << "[" #x "]: ", [](auto... $) {((cerr << $ << "; "), ...); }(x), cerr << '\n' #else #define debug(...) {} #endif using PII = pair; /* * Status: Przetestowane na zadankach * Opis: Find and union z mniejszy do wiekszego * Czas: O(\alpha(n)) oraz O(n) pamięciowo */ struct FindUnion { vector rep; int size(int x) { return -rep[find(x)]; } int find(int x) { return rep[x] < 0 ? x : rep[x] = find(rep[x]); } bool same_set(int a, int b) { return find(a) == find(b); } bool join(int a, int b) { a = find(a), b = find(b); if(a == b) return false; if(-rep[a] < -rep[b]) swap(a, b); rep[a] += rep[b]; rep[b] = a; return true; } FindUnion(int n) : rep(n, -1) {} }; int main() { cin.tie(0)->sync_with_stdio(0); int n; cin >> n; char dd; cin >> dd; vector input(n); REP(i, n) cin >> input[i]; auto to_id = [&](int x, int y) { return x * n + y; }; vector dx, dy; bool multi = false; if(dd == 'N') { dx = {-1, +1, +2, +2, +1, -1, -2, -2}; dy = {+2, +2, +1, -1, -2, -2, -1, +1}; } else if(dd == 'K') { dx = {+1, +1, +1, 0, -1, -1, -1, 0}; dy = {-1, 0, +1, +1, +1, 0, -1, -1}; } else if(dd == 'Q') { dx = {+1, +1, +1, 0, -1, -1, -1, 0}; dy = {-1, 0, +1, +1, +1, 0, -1, -1}; multi = true; } else if(dd == 'R') { dx = {+1, -1, 0, 0}; dy = {0, 0, +1, -1}; multi = true; } else if(dd == 'B') { dx = {+1, -1, +1, -1}; dy = {+1, +1, -1, -1}; multi = true; } vector>> edges(n); REP(i, n) edges[i].resize(n); FindUnion s(n * n); vector vs; REP(i, n) REP(j, n) { if(input[i][j] != '.') { vs.emplace_back(i, j); REP(dir, ssize(dx)) { REP(m, n) { int x = i + (m + 1) * dx[dir]; int y = j + (m + 1) * dy[dir]; if(0 <= x && x < n && 0 <= y && y < n) { if(input[x][y] != '.' && s.join(to_id(i, j), to_id(x, y))) { edges[i][j].emplace_back(x, y); edges[x][y].emplace_back(i, j); } } else break; if(!multi) break; } } } } auto [x1, y1] = vs.back(); if(ssize(vs) == s.size(to_id(x1, y1))) { cout << "YES\n"; vector> deg(n, vector(n)); vector Q; for(auto [x, y] : vs) { if((deg[x][y] = ssize(edges[x][y])) == 1) Q.emplace_back(x, y); } REP(i, ssize(vs) - 1) { auto [x, y] = Q.back(); Q.pop_back(); --deg[x][y]; for(auto &[xx, yy] : edges[x][y]) { if(deg[xx][yy] != 0) { cout << x + 1 << " " << y + 1 << " " << xx + 1 << " " << yy + 1 << "\n"; if(--deg[xx][yy] == 1) { Q.emplace_back(xx, yy); } } } } } else cout << "NO\n"; }