#include #include using namespace std; typedef pair pii; typedef vector vpii; int board_size; char piece_code; struct move{ int xfr, yfr, xto, yto; } gamemoves[10001] = {0}; 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; } vpii getknight(board &board, short x, short y){ vpii 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]) res.push_back(pii(xt, yt)); } return res; } vpii getstraight(board &board, short x, short y, bool king = false){ vpii 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]) res.push_back(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]) res.push_back(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]) res.push_back(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]) res.push_back(pii(xt, yt)); } return res; } vpii getdiagonal(board &board, short x, short y, bool king = false){ vpii res; 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]) res.push_back(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]) res.push_back(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]) res.push_back(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]) res.push_back(pii(xt, yt)); } return res; } vpii getmoves(board &board, short x, short y){ vpii res, vec; switch(piece_code){ case 'N': res = getknight(board, x, y); break; case 'R': res = getstraight(board, x, y); break; case 'B': res = getdiagonal(board, x, y); break; case 'Q': res = getstraight(board, x, y); vec = getdiagonal(board, x, y); res.insert(res.end(), vec.begin(), vec.end()); break; case 'K': res = getstraight(board, x, y, true); vec = getdiagonal(board, x, y, true); res.insert(res.end(), vec.begin(), vec.end()); break; } return res; } bool solve(board br){ vpii moves; if(br.pieces == 1){ return true; } for(int i = 1; i <= board_size; ++i){ for(int j = 1; j <= board_size; ++j){ if(br.b[i][j]){ moves = getmoves(br, i, j); for(auto &mv : moves){ board newbr = br; newbr.remove(i, j); if(solve(newbr)){ gamemoves[newbr.pieces] = {i, j, mv.first, mv.second}; return true; } } } } } return false; } int main (){ ios_base::sync_with_stdio(0); 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); } } } 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; }