#include #include using namespace std; static bool isHorOrVer(vector& rowPositions, vector& colPositions, int i, int j) { return rowPositions[i] == rowPositions[j] || colPositions[i] == colPositions[j]; } static bool isDiag(vector& rowPositions, vector& colPositions, int i, int j) { return abs(rowPositions[i] - rowPositions[j]) == abs(colPositions[i] - colPositions[j]); } static bool isClose(vector& rowPositions, vector& colPositions, int i, int j) { return abs(rowPositions[i] - rowPositions[j]) <= 1 && abs(colPositions[i] - colPositions[j]) <= 1; } static bool isL(vector& rowPositions, vector& colPositions, int i, int j) { int horDiff = abs(colPositions[i] - colPositions[j]); int verDiff = abs(rowPositions[i] - rowPositions[j]); return (horDiff == 1 && verDiff == 2) || (horDiff == 2 && verDiff == 1); } static int getRemainingCount(vector& removed) { int remainingCount = 0; for (int j = 0; j < removed.size(); j++) { if (!removed[j]) { remainingCount++; } } return remainingCount; } static bool check(vector& rowPositions, vector& colPositions, vector& removed, char type, int i, vector& order) { removed[i] = true; order.push_back(i); if (getRemainingCount(removed) == 0) { return true; } for (int j = 0; j < rowPositions.size(); j++) { if (j != i && !removed[j]) { if (type == 'R') { if (isHorOrVer(rowPositions, colPositions, i, j)) { if (check(rowPositions, colPositions, removed, type, j, order)) { return true; } } } else if (type == 'Q') { if (isHorOrVer(rowPositions, colPositions, i, j) || isDiag(rowPositions, colPositions, i, j)) { if (check(rowPositions, colPositions, removed, type, j, order)) { return true; } } } else if (type == 'B') { if (isDiag(rowPositions, colPositions, i, j)) { if (check(rowPositions, colPositions, removed, type, j, order)) { return true; } } } else if (type == 'N') { if (isL(rowPositions, colPositions, i, j)) { if (check(rowPositions, colPositions, removed, type, j, order)) { return true; } } } else if (type == 'K') { if (isClose(rowPositions, colPositions, i, j)) { if (check(rowPositions, colPositions, removed, type, j, order)) { return true; } } } } } removed[i] = false; order.pop_back(); return false; } int main() { std::ios::sync_with_stdio(false); int n; char type; string line; vector rowPositions; vector colPositions; cin >> n >> type; for (int x = 0; x < n; x++) { cin >> line; for (int y = 0; y < n; y++) { if (line[y] != '.') { rowPositions.push_back(x + 1); colPositions.push_back(y + 1); } } } vector removed(rowPositions.size(), false); vector order; bool res = false; for (int i = 0; i < rowPositions.size(); i++) { if (check(rowPositions, colPositions, removed, type, i, order)) { res = true; break; } } if (res) { cout << "YES" << endl; for (int i = 0; i < removed.size(); i++) { if (!removed[i]) { order.push_back(i); break; } } for (int i = order.size() - 1; i >= 1; i--) { cout << rowPositions[order[i]] << " " << colPositions[order[i]] << " " << rowPositions[order[i - 1]] << " " << colPositions[order[i - 1]] << endl; } } else { cout << "NO" << endl; } return 0; }