#include using namespace std; #define all(x) (x).begin(), (x).end() #define pb push_back #define eb emplace_back #define forn(i, n) for (int i = 0; i < (int)n; ++i) #define ford(i, n) for (int i = (int)n - 1; i >= 0; --i) typedef long long ll; typedef pair pi; typedef pair pl; typedef pair pd; typedef vector vi; typedef vector vd; typedef vector vl; typedef vector vvi; typedef vector vii; typedef vector vvii; const ll mod = 1000000007; int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } ll lcm(ll a, ll b) { return a * (b / gcd(a, b)); } ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); } // divide a by b rounded up ll fdiv(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); } // divide a by b rounded down int area[103][103]; int n, piece; bool visited[103][103]; vvi edges(10100); vii res; bool inArea(int posX, int posY) { return (posX >= 0 && posX < n && posY >= 0 && posY < n); } int coordToNum(int posX, int posY) { return posX * n + posY; } pi numToCoord(int num) { return {num / n, num % n}; } void addEdgesK() { int posX, posY; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (area[i][j] != 0) { for (int x = -1; x < 2; x++) { for (int y = -1; y < 2; y++) { if (x == 0 && y == 0) continue; posX = i + x; posY = j + y; if (inArea(posX, posY)) { if (area[posX][posY] != 0) { edges[coordToNum(i, j)].push_back(coordToNum(posX, posY)); } } } } } } } } void addEdgesR() { int posX, posY; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (area[i][j] != 0) { for (int q = -102; q < 102; q++) { if (q == 0) continue; posX = i + q; posY = j; if (inArea(posX, posY)) { if (area[posX][posY] != 0) { edges[coordToNum(i, j)].push_back(coordToNum(posX, posY)); } } posX = i; posY = j + q; if (inArea(posX, posY)) { if (area[posX][posY] != 0) { edges[coordToNum(i, j)].push_back(coordToNum(posX, posY)); } } } } } } } void addEdgesB() { int posX, posY; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (area[i][j] != 0) { for (int q = -102; q < 102; q++) { if (q == 0) continue; posX = i + q; posY = j + q; if (inArea(posX, posY)) { if (area[posX][posY] != 0) { edges[coordToNum(i, j)].push_back(coordToNum(posX, posY)); } } posX = i + q; posY = j - q; if (inArea(posX, posY)) { if (area[posX][posY] != 0) { edges[coordToNum(i, j)].push_back(coordToNum(posX, posY)); } } } } } } } void addEdgesN() { vii moves = {{-1, 2}, {-1, -2}, {1, 2}, {1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}}; int posX, posY; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (area[i][j] != 0) { for (int q = 0; q < moves.size(); ++q) { posX = i + moves[q].first; posY = j + moves[q].second; if (inArea(posX, posY)) { if (area[posX][posY] != 0) { edges[coordToNum(i, j)].push_back(coordToNum(posX, posY)); } } } } } } } void addEdgesQ() { int posX, posY; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (area[i][j] != 0) { for (int q = -102; q < 102; q++) { if (q == 0) continue; posX = i + q; posY = j; if (inArea(posX, posY)) { if (area[posX][posY] != 0) { edges[coordToNum(i, j)].push_back(coordToNum(posX, posY)); } } posX = i; posY = j + q; if (inArea(posX, posY)) { if (area[posX][posY] != 0) { edges[coordToNum(i, j)].push_back(coordToNum(posX, posY)); } } posX = i + q; posY = j + q; if (inArea(posX, posY)) { if (area[posX][posY] != 0) { edges[coordToNum(i, j)].push_back(coordToNum(posX, posY)); } } posX = i + q; posY = j - q; if (inArea(posX, posY)) { if (area[posX][posY] != 0) { edges[coordToNum(i, j)].push_back(coordToNum(posX, posY)); } } } } } } } void DFSUtil(int u, vector &visited, int v) { visited[u] = true; for (int i = 0; i < edges[u].size(); i++) if (!visited[edges[u][i]]) { DFSUtil(edges[u][i], visited, u); } if (u != v) res.push_back({u, v}); } int main() { // . R Q B N K char fig; char tmp; int numOfPieces = 0; cin >> n >> fig; vector visited(n * n, false); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cin >> tmp; if (tmp == '.') area[i][j] = 0; else { numOfPieces++; area[i][j] = 1; } } } if (fig == 'R') { addEdgesR(); } else if (fig == 'Q') { addEdgesQ(); } else if (fig == 'B') { addEdgesB(); } else if (fig == 'N') { addEdgesN(); } else if (fig == 'K') { addEdgesK(); } int curr = -1, prev = -1; for (int i = 0; i < n * n; i++) { if (edges[i].size() > 0) { curr = i; break; } } if (curr == -1) { if (area[0][0] == 0) cout << "NO\n"; else cout << "YES\n"; return 0; } DFSUtil(curr, visited, curr); if (res.size() == numOfPieces - 1) { cout << "YES\n"; for (int i = 0; i < res.size(); i++) { pi from = numToCoord(res[i].first); pi to = numToCoord(res[i].second); cout << from.first + 1 << " " << from.second + 1 << " " << to.first + 1 << " " << to.second + 1 << endl; } } else { cout << "NO\n"; } // for (int i = 0; i < n * n; i++) // { // for (int j = 0; j < (int)edges[i].size(); j++) // { // pi tmp = numToCoord(i); // pi tmp2 = numToCoord(edges[i][j]); // cout << "(" << tmp.first << ", " << tmp.second << ") - (" << tmp2.first << ", " << tmp2.second << ")" << endl; // } // } return 0; }