#include #include #include #include #include using namespace std; int N; char exc; char field[101][101]; int visited[101][101]; struct TreeNode { pair data; vector children; TreeNode* parent = nullptr; }; TreeNode* root = nullptr; enum StepType { Rook, Queen, Bishop, kNight, King }; StepType stepType; set> neighbours(pair act) { set> res; switch (stepType) { case Rook: { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (!(i == act.first && j == act.second) && field[i][j] == 'R') { if (i == act.first) res.insert({i, j}); if (j == act.second) res.insert({i, j}); } } } return res; } case Queen: { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (!(i == act.first && j == act.second) && field[i][j] == 'Q') { int diff = act.first - act.second; int sum = act.first + act.second; if (i - j == diff || i + j == sum || i == act.first || i == act.second) { res.insert({i, j}); } } } } return res; } case Bishop: { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (!(i == act.first && j == act.second) && field[i][j] == 'B') { int diff = act.first - act.second; int sum = act.first + act.second; if (i - j == diff || i + j == sum) res.insert({i, j}); } } } return res; } case kNight: { pair steps[] = { {1,2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}}; for (int i = 0; i < 8; i++) { int next_f = act.first + steps[i].first; int next_s = act.second + steps[i].second; if (next_f < N && next_f >= 0 && next_s < N && next_s >= 0 && field[next_f][next_s] == 'N') { res.insert({next_f, next_s}); } } return res; } case King: { for (int i = -1; i < 2; i++) { for (int j = -1; j < 2; j++) { if (!(i == 0 && j == 0)) { if (act.second + j >= 0 && act.second + j < N && act.first + i >= 0 && act.first + i < N && field[act.first + i][act.second + j] == 'K') { res.insert({i + act.first, j + act.second}); } } } } return res; } } } void bfs(pair start) { root = new TreeNode(); root->data = start; root->parent = root; visited[start.first][start.second] = 1; queue q; q.push(root); while (!q.empty()) { TreeNode* act = q.front(); set> ns = neighbours(act->data); for (set>::iterator i = ns.begin(); i != ns.end(); i++) { if (!visited[i->first][i->second]) { visited[i->first][i->second] = visited[act->data.first][act->data.second] + 1; TreeNode* newNode = new TreeNode(); newNode->parent = act; newNode->data = *i; (act->children).push_back(newNode); q.push(newNode); } } q.pop(); } } void postorder(TreeNode* t) { while (!t->children.empty()) { postorder(t->children.back()); t->children.pop_back(); } if (t == root) return; cout << t->data.first+1 << ' ' << t->data.second+1 << ' ' << t->parent->data.first+1 << ' ' << t->parent->data.second+1 << '\n'; } int main() { cin >> N >> exc; switch (exc) { case 'R': stepType = Rook; break; case 'Q': stepType = Queen; break; case 'B': stepType = Bishop; break; case 'N': stepType = kNight; break; case 'K': stepType = King; break; default: return 1; } pair start = {-1,-1}; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cin >> field[i][j]; if (field[i][j] == exc && start.first == -1) start = {i, j}; } } bfs(start); TreeNode tn = *root; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (field[i][j] == exc && visited[i][j] == 0) { cout << "NO\n"; return 0; } } } cout << "YES\n"; postorder(root); }