#include #include #include using namespace std; typedef pair pii; typedef vector vpii; int board_size; char piece_code; vector output; struct bpiece { int x, y; int index; }; struct move { int xfr, yfr, xto, yto; } gamemoves[10001] = { 0 }; struct board { bpiece* b[101][101] = { 0 }; bpiece pb[10001]; bpiece parents[10001]; vpii connections[10001]; bool visited[10001] = { 0 }; int pieces = 0; void add(short x, short y) { pb[pieces] = { x, y, pieces }; b[x][y] = &(pb[pieces]); 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] != NULL) 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] != NULL) 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] != NULL) 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] != NULL) 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] != NULL) 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] != NULL) 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] != NULL) 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] != NULL) 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] != NULL) 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; } void makeconn(board& board) { for (int i = 0; i < board.pieces; ++i) { board.connections[i] = getmoves(board, board.pb[i].x, board.pb[i].y); } } bool solve(board br, int index) { for (pii& mv : br.connections[index]) { int newix = br.b[mv.first][mv.second]->index; if (br.visited[newix] == false) { br.visited[newix] = true; if (solve(br, newix)) { string res = to_string(br.pb[newix].x) + " " + to_string(br.pb[newix].y) + " " + to_string(br.pb[index].x) + " " + to_string(br.pb[index].y); output.push_back(res); return true; } else { // lisc 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); } } } makeconn(mboard); //mboard.display(); solve(mboard, 0); bool result = output.size() == mboard.pieces - 1; cout << (result ? "YES" : "NO") << "\n"; if (result) { for (auto& str : output) cout << str << "\n"; /*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; }