#include #include #include using namespace std; typedef vector vb; typedef vector vi; typedef vector vvi; void dfs(vvi& g, vb& v, vi& t, vi& q, int x) { v[x] = true; for (int y : g[x]) { if (v[y]) continue; t[y] = x; dfs(g, v, t, q, y); } q.push_back(x); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; string c; cin >> n >> c; vb a(n * n, false); for (int i = 0; i < n; i++) { string s; cin >> s; for (int j = 0; j < n; j++) a[n * i + j] = s[j] != '.'; } // zbudowanie grafu vvi g(n * n); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (!a[n * i + j]) continue; auto add = [&] (int x, int y) { if (x == i && y == j) return; if (x >= 0 && x < n && y >= 0 && y < n && a[n * x + y]) g[n * i + j].push_back(n * x + y); }; if (c == "R") { for (int k = 0; k < n; k++) { add(i, k); } for (int k = 0; k < n; k++) { add(k, j); } } else if (c == "Q") { for (int k = 0; k < n; k++) { add(i, k); } for (int k = 0; k < n; k++) { add(k, j); } for (int k = 1; k < n; k++) { int x = i + k; int y = j + k; add(x, y); } for (int k = 1; k < n; k++) { int x = i + k; int y = j - k; add(x, y); } for (int k = 1; k < n; k++) { int x = i - k; int y = j + k; add(x, y); } for (int k = 1; k < n; k++) { int x = i - k; int y = j - k; add(x, y); } } else if (c == "B") { for (int k = 1; k < n; k++) { int x = i + k; int y = j + k; add(x, y); } for (int k = 1; k < n; k++) { int x = i + k; int y = j - k; add(x, y); } for (int k = 1; k < n; k++) { int x = i - k; int y = j + k; add(x, y); } for (int k = 1; k < n; k++) { int x = i - k; int y = j - k; add(x, y); } } else if (c == "N") { add(i + 1, j + 2); add(i + 1, j - 2); add(i - 1, j + 2); add(i - 1, j - 2); add(i + 2, j + 1); add(i + 2, j - 1); add(i - 2, j + 1); add(i - 2, j - 1); } else if (c == "K") { for (int x = -1; x <= 1; x++) { for (int y = -1; y <= 1; y++) add(i + x, j + y); } } } } vvi h(n * n); for (int x = 0; x < n * n; x++) { for (int y : g[x]) h[y].push_back(x); } // wybranie korzenia vb v(n * n, false); vi t(n * n); vi s; for (int x = 0; x < n * n; x++) { if (a[x] && !v[x]) dfs(g, v, t, s, x); } int r; v = vb(n * n, false); vi q; while (!s.empty()) { int x = s.back(); s.pop_back(); if (v[x]) continue; r = x; dfs(h, v, t, q, r); } // wyznaczenie drzewa v = vb(n * n, false); t = vi(n * n, -1); q = vi(); dfs(h, v, t, q, r); for (int x = 0; x < n * n; x++) { if (a[x] && x != r && t[x] == -1) { cout << "NO\n"; return 0; } } cout << "YES\n"; for (int x : q) { if (x == r) continue; int y = t[x]; cout << (x / n + 1) << " " << (x % n + 1) << " " << (y / n + 1) << " " << (y % n + 1) << "\n"; } return 0; }