#include using namespace std; using ll = long long; using vi = vector; using vll = vector; using pii = pair; using graph = vector; #define FOR(name__, upper__) for (int name__ = 0; name__ < (upper__); ++name__) #define all(x) begin(x), end(x) #define mp make_pair #define mt make_tuple template void initialize_matrix(vector>& matrix, int rows, int cols, T value) { assert(matrix.empty()); FOR (row, rows) matrix.emplace_back(cols, value); } struct coord { int row, col; }; class solver { vector> matrix; vector> vis; vector> solution; char type; vector get_adjacent_K(coord pos) { vector positions; for (int i = -1; i <= 1; i++) for (int j = -1; j <= 1; j++) { coord next = pos; next.row += i; next.col += j; if (to_visit(next)) { positions.push_back(next); } } return positions; } vector get_adjacent_R(coord pos) { vector positions; int n = matrix.size(); FOR (r, n) { if (to_visit({r, pos.col})) positions.push_back({r, pos.col}); } FOR (c, n) { if (to_visit({pos.row, c})) positions.push_back({pos.row, c}); } return positions; } vector get_adjacent_Q(coord pos) { vector positions = get_adjacent_B(pos); auto p = get_adjacent_R(pos); positions.insert(positions.end(), p.begin(), p.end()); return positions; } vector get_adjacent_B(coord pos) { vector positions; int n = matrix.size(); vector dir { { -1, -1 }, { -1, 1 }, {1, 1 }, {1, -1} }; for (coord c : dir) { coord next = pos; while (true) { next.row += c.row; next.col += c.col; if (!valid(next)) break; if (to_visit(next)) positions.push_back(next); } } return positions; } vector get_adjacent_N(coord pos) { vector positions; int n = matrix.size(); vector dir { { -2, -1 }, { -2, 1 }, { 2, -1 }, { 2, 1}, { 1, 2 }, { -1, 2 }, { -1, -2 }, { 1, -2 } }; for (coord c : dir) { coord next = c; next.row += pos.row; next.col += pos.col; if (to_visit(next)) positions.push_back(next); } return positions; } bool valid(coord pos) { return ((unsigned) pos.row < matrix.size() && (unsigned) pos.col < matrix[0].size()); } bool to_visit(coord c) { return valid(c) && matrix[c.row][c.col] && !vis[c.row][c.col]; } void dfs(coord a, coord p) { vis[a.row][a.col] = true; vector adj; switch (type) { case 'K': adj = get_adjacent_K(a); break; case 'R': adj = get_adjacent_R(a); break; case 'Q': adj = get_adjacent_Q(a); break; case 'B': adj = get_adjacent_B(a); break; case 'N': adj = get_adjacent_N(a); break; } for (coord x : adj) { if ( !vis[x.row][x.col] ) dfs(x, a); } if (p.row >= 0 && p.col >= 0) solution.emplace_back(a, p); } public: solver(const vector> &m, char t) : matrix(m), vis(), solution(), type(t) { int n = m.size(); initialize_matrix(vis, n, n, false); } void solve() { int n = matrix.size(); bool finished = false; FOR (row, n) FOR(col, n) { if (to_visit({row, col})) { if (!finished) { dfs({row, col}, {-1, -1}); finished = true; } else { cout << "NO\n"; return; } } } cout << "YES\n"; for (auto &p : solution) { coord a = p.first; coord b = p.second; cout << a.col + 1 << " " << a.row + 1 << " " << b.col + 1 << " " << b.row + 1<< "\n"; } } }; void go() { int n; char type; cin >> n >> type; std::vector> matrix; initialize_matrix(matrix, n, n, false); FOR(r, n) { string row; cin >> row; FOR(c, n) { matrix[r][c] = (row[c] == '.' ? false : true); } } // FOR(r, n) { FOR(c, n) cout << matrix[r][c] << " "; cout << "\n"; } solver s(matrix, type); s.solve(); } int main() { ios::sync_with_stdio(false); cin.tie(0); go(); return 0; }