#include #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); } } } } void dfs(string &result, vector> &edges, set &visited, int N, int cur) { for(int jump: edges[cur]) { if(visited.find(jump) == visited.end()) { visited.insert(jump); dfs(result, edges, visited, N, jump); result.append(to_string(jump / N + 1)); result.append(" "); result.append(to_string(jump % N + 1)); result.append(" "); result.append(to_string(cur / N + 1)); result.append(" "); result.append(to_string(cur % N + 1)); result.append("\n"); } } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int N; char C; cin >> N >> C; string result = ""; vector> edges; set visited; vector vertices; char map[N*N]; for(int x = 0; x < N; x++) { for(int y = 0; y < N; y++) { cin >> map[N*x + y]; if(map[N*x + y] != '.') { vertices.push_back(N * x + y); } edges.push_back(vector()); } } for(int pos: vertices) { vector neighbors; get_neighbors(neighbors, C, {.x = pos / N, .y = pos % N}, N); for(Pos neigh: neighbors) { if(map[N * neigh.x + neigh.y] != '.') { edges[pos].push_back(N * neigh.x + neigh.y); edges[N * neigh.x + neigh.y].push_back(pos); } } } visited.insert(vertices[0]); dfs(result, edges, visited, N, vertices[0]); if(visited.size() == vertices.size()) { cout << "YES" << endl << result << endl; } else { cout << "NO" << endl; } return 0; }