#include #include #include using namespace std; typedef pair pii; int board_size = 0; char piece_code = 0; struct move { int xfr = 0, yfr = 0, xto = 0, yto = 0; } gamemoves[10001]; struct board { bool b[101][101] = { 0 }; int pieces = 0; void add(short x, short y) { b[x][y] = true; pieces++; } void remove(short x, short y) { b[x][y] = false; pieces--; } void display() { cerr << "* "; for (short i = 1; i <= board_size; ++i) cerr << i << " "; cerr << "\n"; for (short i = 1; i <= board_size; ++i) { cerr << i << " "; for (short j = 1; j <= board_size; ++j) cerr << (b[i][j] ? piece_code : '.') << " "; cerr << "\n"; } } }; inline bool onboard(const short& x, const short& y) { return x <= board_size && x >= 1 && y <= board_size && y >= 1; } pii getknight(board& board, short x, short y) { pii res; short knight_x[] = { -1, 1, 2, 2, 1, -1, -2, -2 }; // 8 short knight_y[] = { 2, 2, 1, -1, -2, -2, -1, 1 }; short xt, yt; for (short i = 0; i < 8; ++i) { xt = x + knight_x[i], yt = y + knight_y[i]; if (onboard(xt, yt) && board.b[xt][yt]) return pii(xt, yt); } return pii(-1, -1); } pii getstraight(board& board, short x, short y, bool king = false) { pii res; int max_val = (king ? 1 : board_size - 1); short k, xt, yt; for (k = 1; k <= max_val; ++k) { // up xt = x + k, yt = y; if (!onboard(xt, yt)) break; else if (board.b[xt][yt]) return pii(xt, yt); } for (k = 1; k <= max_val; ++k) { // down xt = x - k, yt = y; if (!onboard(xt, yt)) break; else if (board.b[xt][yt]) return pii(xt, yt); } for (k = 1; k <= max_val; ++k) { // right xt = x, yt = y + k; if (!onboard(xt, yt)) break; else if (board.b[xt][yt]) return pii(xt, yt); } for (k = 1; k <= max_val; ++k) { // left xt = x, yt = y - k; if (!onboard(xt, yt)) break; else if (board.b[xt][yt]) return pii(xt, yt); } return pii(-1, -1); } pii getdiagonal(board& board, short x, short y, bool king = false) { int max_val = (king ? 1 : board_size - 1); short k, xt, yt; for (k = 1; k <= max_val; ++k) { xt = x + k, yt = y + k; if (!onboard(xt, yt)) break; else if (board.b[xt][yt]) return pii(xt, yt); } for (k = 1; k <= max_val; ++k) { xt = x + k, yt = y - k; if (!onboard(xt, yt)) break; else if (board.b[xt][yt]) return pii(xt, yt); } for (k = 1; k <= max_val; ++k) { xt = x - k, yt = y + k; if (!onboard(xt, yt)) break; else if (board.b[xt][yt]) return pii(xt, yt); } for (k = 1; k <= max_val; ++k) { xt = x - k, yt = y - k; if (!onboard(xt, yt)) break; else if (board.b[xt][yt]) return pii(xt, yt); } return pii(-1, -1); } pii getmove(board& board, short x, short y) { pii res; switch (piece_code) { case 'N': return getknight(board, x, y); case 'R': return getstraight(board, x, y); case 'B': return getdiagonal(board, x, y); case 'Q': res = getstraight(board, x, y); if (res.first == -1) res = getdiagonal(board, x, y); return res; case 'K': res = getstraight(board, x, y, true); if (res.first == -1) res = getdiagonal(board, x, y, true); return res; } return pii(-1, -1); } bool solve(board br) { /*if (br.pieces == 1) { return true; }*/ bool possible = true; while (br.pieces > 1) { possible = false; for (int i = 1; i <= board_size; ++i) { for (int j = 1; j <= board_size; ++j) { if (br.b[i][j]) { pii move = getmove(br, i, j); possible = (move.first != -1); if (possible) { //board newbr = br; br.remove(i, j); gamemoves[br.pieces] = { i, j, move.first, move.second }; break; } } } if (possible) break; } if (!possible) return false; } return true; } int main() { ios_base::sync_with_stdio(0); memset(gamemoves, 0, sizeof(gamemoves)); cin >> board_size >> piece_code; char field; board mboard; for (int i = 1; i <= board_size; ++i) { for (int j = 1; j <= board_size; ++j) { cin >> field; if (field != '.') { mboard.add(i, j); } } } //cerr << board_size << " " << piece_code << "\n"; //mboard.display(); bool result = solve(mboard); cout << (result ? "YES" : "NO") << "\n"; if (result) { for (int i = mboard.pieces - 1; i >= 1; --i) { cout << gamemoves[i].xfr << " " << gamemoves[i].yfr << " " << gamemoves[i].xto << " " << gamemoves[i].yto << "\n"; } } return 0; }