#include template void __print(Ts &&...ts){}; #ifdef DEBUG #include "print.hpp" #endif // DEBUG using namespace std; typedef long long ll; typedef long double ld; typedef complex cd; typedef pair pi; typedef pair pl; typedef pair pd; template using vec = vector; typedef vector vi; typedef vector vc; typedef vector vvc; typedef vector vvi; typedef vector vd; typedef vector vvd; typedef vector vl; typedef vector vvl; typedef vector vpi; typedef vector vpl; typedef vector vcd; typedef vector vb; template using pq_max = priority_queue; template using pq_min = priority_queue, greater>; #define FOR(i, a, b) for (int i = a; i < (b); ++i) #define F0R(i, a) for (int i = 0; i < (a); ++i) #define FORd(i, a, b) for (int i = (b)-1; i >= a; --i) #define F0Rd(i, a) for (int i = (a)-1; i >= 0; --i) #define trav(a, x) for (auto &a : x) #define uid(a, b) uniform_int_distribution(a, b)(rng) #define pln( x ) cout << x << "\n" #define ps( x ) cout << x << " " #define entr cout << "\n" #define IN(n) \ int n; \ cin >> n; #define sz(x) (int)(x).size() #define mp make_pair #define pb push_back #define fir first #define sec second #define lb lower_bound #define ub upper_bound #define all(x) x.begin(), x.end() #define ins insert #define beg begin template bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } template bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); template T max(T a, T b, T c) { return max(max(a, b), c); } template T max(T a, Ts... as) { return max(a, max(as...)); } template T min(T a, T b, T c) { return min(min(a, b), c); } template T min(T a, Ts... as) { return min(a, min(as...)); } /////////////////////////////////////////////////////////////////////////////////////////////// /////////////////////////////////////////////////////////////////////////////////////////////// bool is_in(const vvc & M, int x, int y, int n) { if(x >= n || x < 0 || y >= n || y<0) return false; return M[x][y] != '.'; } void add_edge(vvi & G, const vvc & M, int x1, int y1, int x2, int y2, int n) { if(!is_in(M,x1,y1,n)) return; if(!is_in(M,x2,y2,n)) return; int id1 = x1*n + y1; int id2 = x2*n + y2; G[id1].pb(id2); G[id2].pb(id1); } vvi build_rook(const vvc & M, int n) { vvi G(n*n); FOR(i,0,n) { FOR(j,0,n) { int id = i*n + j; if(M[i][j] != '.') { FOR(k,1,n) { add_edge(G,M,i,j,i,j+k,n); add_edge(G,M,i,j,i+k,j,n); } } } } return G; } vvi build_queen(const vvc & M, int n) { vvi G(n*n); FOR(i,0,n) { FOR(j,0,n) { int id = i*n + j; if(M[i][j] != '.') { FOR(k,1,n) { add_edge(G,M,i,j,i,j+k,n); add_edge(G,M,i,j,i+k,j,n); add_edge(G,M,i,j,i+k,j-k,n); add_edge(G,M,i,j,i+k,j+k,n); } } } } return G; } vvi build_bishop(const vvc & M, int n) { vvi G(n*n); FOR(i,0,n) { FOR(j,0,n) { int id = i*n + j; if(M[i][j] != '.') { FOR(k,1,n) { add_edge(G,M,i,j,i-k,j+k,n); add_edge(G,M,i,j,i+k,j+k,n); } } } } return G; } vvi build_knight(const vvc & M, int n) { vvi G(n*n); FOR(i,0,n) { FOR(j,0,n) { int id = i*n + j; if(M[i][j] != '.') { add_edge(G,M,i,j,i-2,j+1,n); add_edge(G,M,i,j,i-1,j+2,n); add_edge(G,M,i,j,i+1,j+2,n); add_edge(G,M,i,j,i+2,j+1,n); } } } return G; } vvi build_king(const vvc & M, int n) { vvi G(n*n); FOR(i,0,n) { FOR(j,0,n) { int id = i*n + j; if(M[i][j] != '.') { add_edge(G, M, i,j,i,j+1,n); add_edge(G, M,i,j,i+1,j,n); add_edge(G, M,i,j,i+1,j+1,n); add_edge(G, M,i,j,i+1,j-1,n); } } } return G; } void dfs(const vvi & G, vi & d, vi & prev, int v) { FOR(i, 0, sz(G[v])) { if(d[G[v][i]] == -1) { d[G[v][i]] = d[v]+1; prev[G[v][i]] = v; dfs(G, d, prev, G[v][i]); } } } void solution() { int n; char a; cin>>n>>a; vvc M(n, vc(n)); FOR(i,0,n) { FOR(j,0,n) { cin>>M[i][j]; } } vvi G; if(a == 'K') { G = build_king(M, n); } else if(a == 'Q') { G = build_queen(M,n); } else if(a == 'R') { G = build_rook(M, n); } else if(a == 'N') { G = build_knight(M, n); } else if(a == 'B') { G = build_bishop(M, n); } __print(G); int s = -1; vi d(n*n, -1); vi prev(n*n, -1); FOR(i,0,n) { FOR(j,0,n) { if(M[i][j] != '.' && d[i*n+j] == -1) { if(s != -1) { pln("NO"); return; } s = i*n+j; prev[s] = -1; d[s] = 0; dfs(G, d, prev, s); } } } //__print(d); vi ord(n*n); FOR(i,0,n*n) ord[i]=i; sort(all(ord), [d](int a, int b) { return d[a] > d[b]; }); //__print(ord); //__print(prev); vector> res; FOR(i,0,n*n) { if(d[ord[i]] > 0) { res.pb({ { ord[i]/n, ord[i]%n }, { prev[ord[i]]/n, prev[ord[i]]%n } }); } } pln("YES"); pln(res.size()); FOR(i,0,sz(res)) { ps(res[i].first.first+1);ps(res[i].first.second+1);ps(res[i].second.first+1);pln(res[i].second.second+1); } } int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); int qs = 1; // cin >> qs; while (qs--) { solution(); } return 0; }