#include using namespace std; __attribute__((always_inline)) bool present(const std::vector& T, int val) { return T[val] != 0; } __attribute__((always_inline)) void process2 (std::vector>& G, const vector& T, int N, int idx, int i, int j, int idx2, int i2, int j2) { assert(idx == i*N+j); assert(idx2 == i2*N+j2); assert(present(T, idx)); if (i2 >= 0 && i2 < N && j2 >= 0 && j2 < N) { if (present(T, idx2)) { G[idx].push_back(idx2); G[idx2].push_back(idx); } } } bool rek(std::vector>& MO, std::vector& volte, const std::vector>&G, std::vector& T, int N, int a) { if (volte[a]) { return false; } volte[a] = true; for (int b: G[a]) { if (!present(T, b)) { continue; } if (rek(MO, volte, G, T, N, b)) { MO.emplace_back(b, a); } } return true; } int main() { int N; cin >> N; char strategy = '.'; { string strategy_s; cin >> strategy_s; strategy = strategy_s[0]; } vector T(N*N, 0); for (int i = 0; i < N; i++) { string line; cin >> line; for (int j = 0; j < N; j++) { char c = line[j]; if (c != '.') { T[i*N+j] = 1; } } } vector> G(N*N); int idx = 0; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { assert(i*N+j == idx); if (present(T, idx)) { if (strategy == 'K') { int dx = -1, dy = -1; for (int k = 0; k < 9; k++) { #define PROC(dx, dy) process2(G, T, N, idx, i, j, idx + dx*N+dy, i+dx, j+dy) if (dx != 0 || dy != 0) { PROC(dx, dy); } dx++; if (dx == 2) { dx = -1; dy++; } } assert(dx == -1 && dy == 2); } if (strategy == 'Q' || strategy == 'B') { for (int k = -N+1; k < N; k++) { if (k == 0) { continue; } PROC(+k, -k); PROC(+k, +k); } } if (strategy == 'Q' || strategy == 'R') { for (int k = -N+1; k < N; k++) { if (k == 0) { continue; } PROC(+k, 0); PROC(0, +k); } } if (strategy == 'N') { assert(strategy == 'N'); PROC(+2, -1); PROC(+2, +1); PROC(+1, -2); PROC(+1, +2); PROC(-1, -2); PROC(-1, +2); PROC(-2, -1); PROC(-2, +1); } } idx++; } } int start_idx = -1; for (int idx = 0; idx < N*N; idx++) { if (present(T, idx)) { start_idx = idx; break; } } if (start_idx == -1) { assert(false); // TODO return 0; } std::vector> MO; vector volte(N); for (int i = 0; i < N*N; i++) { if (!present(T, i)) { volte[i] = true; } } rek(MO, volte, G, T, N, start_idx); for (int i = 0; i < N*N; i++) { bool v = volte[i]; if (!v) { cout << "NO\n"; return 0; } } cout << "YES\n"; for (auto [b,a] : MO) { int i0, j0, i1, j1; i0 = b/N; j0 = b%N; i1 = a/N; j1 = a%N; cout << i0+1 << " " << j0+1 << " " << i1+1 << " " << j1+1 << "\n"; } return 0; }