#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #ifdef __ACM_CHS__ #include "common.h" #define Trace(...) \ do \ { \ std::cerr << format ( __VA_ARGS__ ); \ std::cerr . flush (); \ } \ while ( 0 ) #else #define Trace(...) #endif /* __ACM_CHS__ */ //------------------------------------------------------------------------------------------------- using namespace std; map,set>> graph; bool seo(const pair& p1, const pair& p2, char c) { switch(c) { case 'K': return abs(p1.first-p2.first) <= 1 && abs(p1.second-p2.second) <= 1; case 'Q': return p1.first == p2.first || p1.second == p2.second || (abs(p1.first-p2.first) == abs(p1.second-p2.second)); case 'R': return p1.first == p2.first || p1.second == p2.second; case 'B': return abs(p1.first - p2.first) == abs(p1.second - p2.second); case 'N': { int x = abs(p1.first - p2.first); int y = abs(p1.second - p2.second); return (x == 1 && y == 2) || (x == 2 && y == 1); } default: throw; } } int main ( void ) { std::ios::sync_with_stdio ( false ); std::cin . tie ( 0 ); int n; string s; cin >> n >> s; vector m(n,""); for(int i = 0; i < n; ++i) cin >> m[i]; vector> pts; for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) if(m[i][j] == s[0]) { graph[{i,j}] = {}; pts.emplace_back(i,j); } for(size_t i = 0; i < pts.size(); ++i) for(size_t j = i + 1; j < pts.size(); ++j) if(seo(pts[i],pts[j],s[0])) { graph[pts[i]].insert(pts[j]); graph[pts[j]].insert(pts[i]); } vector> result; while(graph.size() > 1) { size_t deg = 2*n*n; pair min_idx; for(auto& vertex : graph) if(vertex.second.size() < deg) { min_idx = vertex.first; deg = vertex.second.size(); } if(deg == 0) { cout << "NO" << endl; return 0; } auto& moving_from = graph[min_idx]; result.emplace_back(min_idx.first,min_idx.second, moving_from.begin()->first,moving_from.begin()->second); for(auto& nei: moving_from) graph[nei].erase(min_idx); graph.erase(min_idx); } cout << "YES" << endl; for(auto& t : result) cout << get<0>(t) + 1 << " " << get<1>(t) + 1 << " " << get<2>(t) + 1 << " " << get<3>(t) + 1 << endl; return 0; }