#include using namespace std; #define ll long long #define debug(args...) \ cout << "#" << __LINE__ << ": "; \ __dbg(__split(#args, ',').begin(), args); vector __split(const string& s, char c) { vector v; stringstream ss(s); string x; while (getline(ss, x, c)) if (x!="") v.emplace_back(x); return move(v); } template inline string __to_str(T x) { stringstream ss; ss << "["; for (auto it = x.begin(); it != x.end(); it++) { if (it != x.begin()) ss << " "; ss << (*it); } ss << "]"; return ss.str(); } template inline string __to_str(stack x) { stringstream ss; ss << "["; bool first = 1; while (!x.empty()) { if (!first) ss << " "; ss << x.top(); x.pop(); first = 0; } ss << "]"; return ss.str(); } template ostream &operator<<(ostream &ostr, const pair p) { ostr << "(" << p.first << "," << p.second << ")"; return ostr; } template inline void __dbg_var(vector x) { cout << __to_str(x); } template inline void __dbg_var(list x) { cout << __to_str(x); } template inline void __dbg_var(set x) { cout << __to_str(x); } template inline void __dbg_var(unordered_set x) { cout << __to_str(x); } template inline void __dbg_var(stack x) { cout << __to_str(x); } template inline void __dbg_var(T val) { cout << val; } inline void __dbg(vector::iterator it) { cout << endl; } template inline void __dbg(vector::iterator it, T a, Args... args) { cout << it->substr((*it)[0] == ' ', it->length()) << "="; __dbg_var(a); cout << " "; __dbg(++it, args...); } const int MOD = 1e9+7; // x^n mod m ll _modpow(ll x, ll n, ll m = MOD) { if (n == 0) return 1 % m; ll u = _modpow(x,n/2,m); u = (u*u)%m; if (n & 1) u = (u*x)%m; return u; } auto speedup=[](){ std::ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); return nullptr; }(); //----------------the actual program starts here---------------- vector> R_moves = { {-1,0}, {1,0}, {0,-1}, {0,1} }; vector> Q_moves = { {-1,0}, {1,0}, {0,-1}, {0,1}, {-1,-1}, {1,1}, {-1,1}, {1,-1} }; vector> B_moves = { {-1,-1}, {1,1}, {-1,1}, {1,-1} }; vector> N_moves = { {-2,1}, {-2,-1}, {-1,-2}, {1,-2}, {-1,2}, {1,2}, {2,-1}, {2,1} }; vector> K_moves = { {-1,-1}, {0,-1}, {1,-1}, {1,0}, {1,1}, {0,1}, {-1,1}, {-1,0} }; const int MAX_N = 100; char grid[MAX_N][MAX_N]; int N; char t; vector pos; int id = 0; unordered_map mp1; unordered_map mp2; vector> *type; vector> dir; void dfs(vector> &adj, int u, vector &seen, int &count) { count++; seen[u] = true; for (auto v : adj[u]) if (!seen[v]) dfs(adj, v, seen, count); } void dfs(vector> &adj, int u, int p, vector &popped, vector &seen) { //debug(u, p, seen[u], popped[u]); seen[u] = true; for (int v : adj[u]) if (seen[v] == false) dfs(adj, v, u, popped, seen); bool all_neigh_seen = true; for (int v : adj[u]) if (seen[v] == false) { all_neigh_seen = false; break; } if (adj[u].size() == 0 || all_neigh_seen && p != -1) { popped[u] = true; int pos_u = mp1[u]; int pos_p = mp1[p]; int y1 = pos_u / N + 1; int x1 = pos_u % N + 1; int y2 = pos_p / N + 1; int x2 = pos_p % N + 1; cout << y1 << " " << x1 << " " << y2 << " " << x2 << '\n'; return; } } int main() { cin >> N >> t; if (t=='K') { type = &K_moves; } else if (t=='N') { type = &N_moves; } else if (t=='B') { type = &B_moves; } else if (t=='Q') { type = &Q_moves; } else if (t=='R') { type = &R_moves; } dir = *type; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { cin >> grid[i][j]; if (grid[i][j] != '.') { pos.push_back(i*N+j); mp1[id] = i*N+j; mp2[i*N+j] = id; id++; } } } vector> adj(pos.size()); for (auto curr : pos) { int curr_id = mp2[curr]; int y = curr / N; int x = curr % N; if (t == 'N' || t == 'K') { for (int i = 0; i < dir.size(); i++) { int yy = y + dir[i][0]; int xx = x + dir[i][1]; if (yy < 0 || xx < 0 || yy >= N || xx >= N) continue; if (grid[yy][xx] != '.') { int id_neigh = mp2[yy*N+xx]; adj[curr_id].push_back(id_neigh); //adj[id_neigh].push_back(curr_id); } } } else { for (int i = 0; i < dir.size(); i++) { int yy = y; int xx = x; bool first = false; while (1) { if (yy < 0 || xx < 0 || yy >= N || xx >= N) break; if (grid[yy][xx] != '.' && first) { int id_neigh = mp2[yy*N+xx]; adj[curr_id].push_back(id_neigh); //adj[id_neigh].push_back(curr_id); } first = true; yy += dir[i][0]; xx += dir[i][1]; } } } } for (int i = 0; i < adj.size(); i++) { cout << i << " | "; for (auto n : adj[i]) cout << n << " "; cout << '\n'; } /*for (int i = 0; i < adj.size(); i++) if (adj[i].size() == 0) { cout << "NO"; return 0; }*/ int count = 0; vector seen(adj.size(), false); dfs(adj, 0, seen, count); if (count != adj.size()) { cout << "NO"; } else { cout << "YES"; if (pos.size() > 1) cout << "\n"; else return 0; vector popped(adj.size(), false); vector seen(adj.size(), false); dfs(adj, 0, -1, popped, seen); } return 0; }