#include using namespace std; typedef long long ll; struct Pos { int x; int y; }; struct Move { Pos from; Pos to; }; vector get_directions(char excavator){ vector dirs; switch (excavator){ case 'R': dirs.push_back({0, 1}); dirs.push_back({0, -1}); dirs.push_back({1, 0}); dirs.push_back({-1, 0}); break; case 'Q': dirs.push_back({0, 1}); dirs.push_back({0, -1}); dirs.push_back({1, 0}); dirs.push_back({-1, 0}); dirs.push_back({1, 1}); dirs.push_back({-1, -1}); dirs.push_back({1, -1}); dirs.push_back({-1, 1}); break; case 'B': dirs.push_back({1, 1}); dirs.push_back({-1, -1}); dirs.push_back({1, -1}); dirs.push_back({-1, 1}); break; case 'K': dirs.push_back({0, 1}); dirs.push_back({0, -1}); dirs.push_back({1, 0}); dirs.push_back({-1, 0}); dirs.push_back({1, 1}); dirs.push_back({-1, -1}); dirs.push_back({1, -1}); dirs.push_back({-1, 1}); break; case 'N': dirs.push_back({1, 2}); dirs.push_back({-1, -2}); dirs.push_back({1, -2}); dirs.push_back({-1, 2}); dirs.push_back({2, 1}); dirs.push_back({-2, -1}); dirs.push_back({-2, 1}); dirs.push_back({2, -1}); break; } return dirs; } Pos sum_pos(Pos p1, Pos p2){ return {p1.x + p2.x, p1.y + p2.y}; } bool in_bounds(Pos p, int size){ return (p.x >= 0 && p.y >= 0 && p.x < size && p.y < size); } void get_neighbors(vector &neighbors, char excavator, Pos pos, int size){ vector dirs = get_directions(excavator); if (excavator == 'N' || excavator == 'K'){ for (Pos dir : dirs){ Pos tmp = sum_pos(pos, dir); if (in_bounds(tmp, size)){ neighbors.push_back(tmp); } } } else { for (Pos dir : dirs){ Pos tmp = sum_pos(pos, dir); while (in_bounds(tmp, size)){ neighbors.push_back(tmp); tmp = sum_pos(tmp, dir); } } } } vector result; bool DFS(Pos pos, char excavator, vector> &visited, vector> &matrix, int N, int pieces){ if (pieces == 0) return true; visited[pos.x][pos.y] = true; vector neighbors; get_neighbors(neighbors, excavator, pos, N); for (Pos neighbor : neighbors){ if (matrix[neighbor.x][neighbor.y] == excavator && !visited[neighbor.x][neighbor.y]){ Move mov = {pos, neighbor}; result.push_back(mov); if (DFS(neighbor, excavator, visited, matrix, N, pieces - 1)){ return true; } result.pop_back(); } } visited[pos.x][pos.y] = false; return false; } bool DFS_init(char excavator, vector> &matrix, int N){ vector> visited(N); queue q; int pieces = 0; for (int i = 0; i < N; i++){ for (int j = 0; j < N; j++){ visited[i].push_back(0); if (matrix[i][j] == excavator){ Pos pos = {i, j}; q.push(pos); pieces++; } } } while(!q.empty()){ Pos p = q.front(); q.pop(); if (DFS(p, excavator, visited, matrix, N, pieces - 1)){ return true; } } return false; } int main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); int N; char excavator; cin >> N >> excavator; vector> matrix(N); for (int i = 0; i < N; i++){ for (int j = 0; j < N; j++){ char c; cin >> c; matrix[i].push_back(c); } } if (DFS_init(excavator, matrix, N)){ cout << "YES" << endl; for (Move mov : result){ cout << mov.from.x + 1 << " " << mov.from.y + 1 << " " << mov.to.x + 1 << " " << mov.to.y + 1 << endl; } } else { cout << "NO" << endl; } return 0; }