//#pragma GCC optimize ("O0") //#pragma GCC optimize("Ofast,unroll-loops") //#pragma GCC target("avx,avx2,fma") #include #define all(x) x.begin(), x.end() #define UN -1 #define VIS -2 #define EX -3 #define mp(a, b) make_pair(a, b) #define pb push_back #define pob pop_back() #define puf push_front #define pof pop_front() #define clr(a) (a).clear() #define sz(a) (int)(a).size() #define forn(t, n) for(int t = 0; t < n; t++) #define foren(t, n) for(int t = 1; t <= n; t++) #define llm LONG_LONG_MAX #define llmn LONG_LONG_MIN #define intm INT_MAX #define intmn INT_MIN #define dblm DBL_MAX #define dblmn DBL_MIN #define mod 1000000007 #define mod2 1000000009 #define mil 1111111 #define bil 1111111111 #define pi M_PI #define euler 2.718281828459 #define eps 1e-9 #define inf (int)(2e9) #define llinf (long long)(2e18) #define degrad (pi/180.0) #define raddeg (180.0/pi) #define uset unordered_set #define umap unordered_map #define fio ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); using namespace std; typedef long long ll; typedef vector vll; typedef pair pll; typedef vector vpll; typedef vector vi; typedef pair ii; typedef vector vii; typedef vector vvi; typedef pair iii; typedef pair iiii; typedef pair tll; typedef vector vvii; typedef vector vvll; typedef vector vc; typedef vector vvc; typedef vector vb; typedef vector vvb; typedef queue qi; typedef queue qll; typedef queue qii; typedef vector vtll; typedef vector viii; typedef pair ppll; typedef priority_queue pqi; typedef priority_queue pqll; typedef pair iii; typedef vector vs; typedef vector vd; typedef pair dd; typedef vector
vdd; typedef pair riii; typedef vector > vvd; typedef vector vvvi; //ifstream in("/home/danza/CLionProjects/codeforces/in.in"); //ofstream out("/home/danza/CLionProjects/codeforces/out2.out"); //#define cin in //#define cout out template ostream& operator << (ostream &out, const vector &v) { for(auto it = v.begin(); it != v.end(); ++it) { if (it == v.begin()) out << *it; else out << " " << *it; } return out; } int n; char type; vvi G; vs grid; int name(ii x) { return x.first * n + x.second; } bool inside(int x, int y) { return 0 <= x && x < n && 0 <= y && y < n; } void add_to_graph(vi &curr) { for(int i = 0; i < sz(curr) - 1; i++) { int a = curr[i], b = curr[i + 1]; G[a].push_back(b); G[b].push_back(a); } } void build_r() { vi curr; for(int r = 0; r < n; r++) { clr(curr); for(int c = 0; c < n; c++) if(grid[r][c] != '.') curr.push_back(name({r, c})); add_to_graph(curr); } for(int c = 0; c < n; c++) { clr(curr); for(int r = 0; r < n; r++) if(grid[r][c] != '.') curr.push_back(name({r, c})); add_to_graph(curr); } } void build_b() { vi curr; for(int r = 0; r < n; r++) { clr(curr); for(int c = 0; c <= r; c++) { int tr = r - c, tc = c; if(!inside(tr, tc)) break; if(grid[tr][tc] != '.') curr.push_back(name({tr, tc})); } add_to_graph(curr); } for(int c = 1; c < n; c++) { clr(curr); for(int r = n - 1; r >= 0; r--) { int tr = r, tc = n - r; if(!inside(tr, tc)) break; if(grid[tr][tc] != '.') curr.push_back(name({tr, tc})); } add_to_graph(curr); } for(int r = n - 1; r >= 0; r--) { clr(curr); for(int c = 0; c < n - r; c++) { int tr = r + c, tc = c; if(!inside(tr, tc)) break; if(grid[tr][tc] != '.') curr.push_back(name({tr, tc})); } add_to_graph(curr); } for(int c = 1; c < n; c++) { clr(curr); for(int r = 0; r < n; r++) { int tr = r, tc = r + c; if(!inside(tr, tc)) break; if(grid[tr][tc] != '.') curr.push_back(name({tr, tc})); } add_to_graph(curr); } } void build_q() { build_r(); build_b(); } void build_n() { int dr[] = {-2, -1, 1, 2, 2, 1, -1, -2}, dc[] = {1, 2, 2, 1, -1, -2, -2, -1}; for(int r = 0; r < n; r++) { for(int c = 0; c < n; c++) { if(grid[r][c] != '.') { int a = name({r, c}); for (int dir = 0; dir < 8; dir++) { int tr = r + dr[dir], tc = c + dc[dir]; if(inside(tr, tc) && grid[tr][tc] != '.') { int b = name({tr, tc}); G[a].push_back(b); } } } } } } void build_k() { int dr[] = {-1, -1, 0, 1, 1, 1, 0, -1}, dc[] = {0, 1, 1, 1, 0, -1, -1, -1}; for(int r = 0; r < n; r++) { for(int c = 0; c < n; c++) { if(grid[r][c] != '.') { int a = name({r, c}); for(int dir = 0; dir < 8; dir++) { int tr = r + dr[dir], tc = c + dc[dir]; if(inside(tr, tc) && grid[tr][tc] != '.') { int b = name({tr, tc}); G[a].push_back(b); } } } } } } int V, children, root, cnt; vi num, low, parent; uset art; uset left_v; void ap(int u) { num[u] = low[u] = cnt++; forn(i, sz(G[u])) { int v = G[u][i]; if (num[v] == UN && left_v.count(v)) { if (u == root) children++; parent[v] = u; ap(v); if (num[u] <= low[v]) art.insert(u); low[u] = min(low[u], low[v]); } else if(v != parent[u]) { low[u] = min(low[u], num[v]); } } } vi vis; void dfs(int u) { vis[u] = 1; forn(i, sz(G[u])) { int v = G[u][i]; if(!vis[v]) dfs(v); } } int main() { fio cin >> n >> type; grid.resize(n); int vertices = 0; forn(i, n) { cin >> grid[i]; forn(j, n) { if(grid[i][j] != '.') { vertices++; left_v.insert(name({i, j})); } } } G.resize(n * n + 1); if(type == 'R') build_r(); else if(type == 'Q') build_q(); else if(type == 'B') build_b(); else if(type == 'N') build_n(); else build_k(); V = n * n; int components = 0; vis.assign(n * n, 0); for(auto &x: left_v) { if(!vis[x]) { dfs(x); components++; } } if(components > 1) { cout << "NO\n"; } else { vector, pair>> ans; forn(i, vertices - 1) { clr(art); num.assign(V, UN); low.assign(V, intm); parent.assign(V, -1); children = 0; root = *(left_v.begin()); cnt = 0; ap(root); if(children > 1) art.insert(root); // else // art.erase(root); int erased = -1; for(auto &x: left_v) { if(!art.count(x)) { for(int k = 0; k < sz(G[x]); k++) { int y = G[x][k]; if(left_v.count(y)) { ans.push_back({{x / n, x % n}, {y / n, y % n}}); erased = x; break; } } } if(erased != -1) break; } if(erased == -1) { cout << "NO\n"; return 0; } else { left_v.erase(erased); } } cout << "YES\n"; for(auto &x: ans) { cout << x.first.first + 1 << ' ' << x.first.second + 1 << ' ' << x.second.first + 1 << ' ' << x.second.second + 1 << '\n'; } } return 0; }