#include using namespace std; string type; string recursion(set> e, string retval) { if (e.size() == 1) { return retval; } int num = 0; for (auto e1 : e) { for (auto e2 : e) { if (e1 == e2) { continue; } int x = e1.first - e2.first; int y = e1.second - e2.second; if (type == "R") { if (x == 0 || y == 0) { set> ee2; for (auto elem : e) { ee2.insert(elem); } ee2.erase(e1); string retval2 = retval; retval2 += to_string(e1.first + 1) + " " + to_string(e1.second + 1) + " " + to_string(e2.first + 1) + " " + to_string(e2.second + 1) + "\n"; string ret = recursion(ee2, retval2); if (ret.compare("NO\n") != 0) { return ret; } } } if (type == "Q") { if (x == 0 || y == 0 || abs(x) == abs(y)) { set> ee2; for (auto elem : e) { ee2.insert(elem); } ee2.erase(e1); string retval2 = retval; retval2 += to_string(e1.first + 1) + " " + to_string(e1.second + 1) + " " + to_string(e2.first + 1) + " " + to_string(e2.second + 1) + "\n"; string ret = recursion(ee2, retval2); if (ret.compare("NO\n") != 0) { return ret; } } } if (type == "B") { if (abs(x) == abs(y)) { set> ee2; for (auto elem : e) { ee2.insert(elem); } ee2.erase(e1); string retval2 = retval; retval2 += to_string(e1.first + 1) + " " + to_string(e1.second + 1) + " " + to_string(e2.first + 1) + " " + to_string(e2.second + 1) + "\n"; string ret = recursion(ee2, retval2); if (ret.compare("NO\n") != 0) { return ret; } } } if (type == "N") { if ((abs(x) == 1 && abs(y) == 2) || (abs(x) == 2 && abs(y) == 1)) { int xdir, ydir; if (e2.first > e1.first) { xdir = 1; } else { xdir = -1; } if (e2.second > e1.second) { ydir = 1; } else { ydir = -1; } int overlap = false; int xdiff = 0, ydiff = 0; for (int x1 = 0; x1 < abs(x); x1++) { xdiff++; if (e.find(make_pair(e1.first + xdiff, e1.second + ydiff)) != e.end()) { overlap = true; break; } } for (int y1 = 0; y1 < abs(y) - 1; y1++) { ydiff++; if (e.find(make_pair(e1.first + xdiff, e1.second + ydiff)) != e.end()) { overlap = true; break; } } if (overlap == true) { overlap = false; xdiff = 0, ydiff = 0; for (int y1 = 0; y1 < abs(y); y1++) { ydiff++; if (e.find(make_pair(e1.first + xdiff, e1.second + ydiff)) != e.end()) { overlap = true; break; } } for (int x1 = 0; x1 < abs(x) - 1; x1++) { xdiff++; if (e.find(make_pair(e1.first + xdiff, e1.second + ydiff)) != e.end()) { overlap = true; break; } } } if (overlap == false) { set> ee2; for (auto elem : e) { ee2.insert(elem); } ee2.erase(e1); string retval2 = retval; retval2 += to_string(e1.first + 1) + " " + to_string(e1.second + 1) + " " + to_string(e2.first + 1) + " " + to_string(e2.second + 1) + "\n"; string ret = recursion(ee2, retval2); if (ret.compare("NO\n") != 0) { return ret; } } } } if (type == "K") { if (x == 0 || y == 0 || abs(x) == abs(y)) { bool overlap = false; if (x == 0) { for (int y1 = min(e1.second, e2.second) + 1; y1 < max(e1.second, e2.second); y1++) { if (e.find(make_pair(x, y1)) != e.end()) { overlap = true; break; } } } if (y == 0) { for (int x1 = min(e1.first, e2.first) + 1; x1 < max(e1.first, e2.first); x1++) { if (e.find(make_pair(x1, y)) != e.end()) { overlap = true; break; } } } if (abs(x) == abs(y)) { int xdir, ydir; if (e2.first > e1.first) { xdir = 1; } else { xdir = -1; } if (e2.second > e1.second) { ydir = 1; } else { ydir = -1; } int xdiff = xdir, ydiff = ydir; for (int i = 0; i < abs(x) - 1; i++) { if (e.find(make_pair(e1.first + xdiff, e1.second + ydiff)) != e.end()) { overlap = true; break; } xdiff += xdir; ydiff += ydir; } } if (overlap == false) { set> ee2; for (auto elem : e) { ee2.insert(elem); } ee2.erase(e1); string retval2 = retval; retval2 += to_string(e1.first + 1) + " " + to_string(e1.second + 1) + " " + to_string(e2.first + 1) + " " + to_string(e2.second + 1) + "\n"; string ret = recursion(ee2, retval2); if (ret.compare("NO\n") != 0) { return ret; } } } } } } return "NO\n"; } int main() { ios::sync_with_stdio(false); char board[101][101]; int n; set> e; cin >> n >> type; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> board[i][j]; if (board[i][j] != '.') { e.insert(make_pair(i, j)); } } } cout << recursion(e, "YES\n"); }