#include #include #include #include using namespace std; constexpr int MAXN = 101; int n; int mat[MAXN][MAXN]; vector edges[MAXN]; int x[MAXN * MAXN], y[MAXN * MAXN]; vector> steps; bitset bio; bool check(int i, int j) { return i >= 0 && i < n && j >= 0 && j < n; } void horiz(int i, int j) { for (int k = 1; check(i + k, j); ++k) { if (mat[i + k][j] >= 0) { edges[mat[i + k][j]].push_back(mat[i][j]); } } for (int k = 1; check(i - k, j); ++k) { if (mat[i - k][j] >= 0) { edges[mat[i - k][j]].push_back(mat[i][j]); } } for (int k = 1; check(i, j + k); ++k) { if (mat[i][j + k] >= 0) { edges[mat[i][j + k]].push_back(mat[i][j]); } } for (int k = 1; check(i, j - k); ++k) { if (mat[i][j - k] >= 0) { edges[mat[i][j - k]].push_back(mat[i][j]); } } } void diag(int i, int j) { for (int k = 1; check(i + k, j + k); ++k) { if (mat[i + k][j + k] >= 0) { edges[mat[i + k][j + k]].push_back(mat[i][j]); } } for (int k = 1; check(i - k, j + k); ++k) { if (mat[i - k][j + k] >= 0) { edges[mat[i - k][j + k]].push_back(mat[i][j]); } } for (int k = 1; check(i + k, j - k); ++k) { if (mat[i + k][j - k] >= 0) { edges[mat[i + k][j - k]].push_back(mat[i][j]); } } for (int k = 1; check(i - k, j - k); ++k) { if (mat[i - k][j - k] >= 0) { edges[mat[i - k][j - k]].push_back(mat[i][j]); } } } void horse(int i, int j) { if (check(i + 2, j + 1) && mat[i + 2][j + 1] >= 0) { edges[mat[i + 2][j + 1]].push_back(mat[i][j]); } if (check(i + 1, j + 2) && mat[i + 1][j + 2] >= 0) { edges[mat[i + 1][j + 2]].push_back(mat[i][j]); } if (check(i - 2, j + 1) && mat[i - 2][j + 1] >= 0) { edges[mat[i - 2][j + 1]].push_back(mat[i][j]); } if (check(i - 1, j + 2) && mat[i - 1][j + 2] >= 0) { edges[mat[i - 1][j + 2]].push_back(mat[i][j]); } if (check(i + 2, j - 1) && mat[i + 2][j - 1] >= 0) { edges[mat[i + 2][j - 1]].push_back(mat[i][j]); } if (check(i + 1, j - 2) && mat[i + 1][j - 2] >= 0) { edges[mat[i + 1][j - 2]].push_back(mat[i][j]); } if (check(i - 2, j - 1) && mat[i - 2][j - 1] >= 0) { edges[mat[i - 2][j - 1]].push_back(mat[i][j]); } if (check(i - 1, j - 2) && mat[i - 1][j - 2] >= 0) { edges[mat[i - 1][j - 2]].push_back(mat[i][j]); } } void king(int i, int j) { for (int a = -1; a <= 1; ++a) for (int b = -1; b <= 1; ++b) { if ((a || b) && check(i + a, j + b) && mat[i + a][j + b] >= 0) { edges[mat[i + a][j + b]].push_back(mat[i][j]); } } } void dfs(int i) { bio.set(i); for (int j: edges[i]) { if (!bio[j]) { steps.emplace_back(j, i); dfs(j); } } } int main() { // ios_base::sync_with_stdio(false); // cin.tie(nullptr); char type, c; int m = 0; cin>>n>>type; for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) { cin>>c; if (c == type) { mat[i][j] = m; x[m] = i + 1; y[m] = j + 1; ++m; } else { mat[i][j] = -1; } } for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (mat[i][j] >= 0) { switch (type) { case 'R': horiz(i, j); break; case 'Q': horiz(i, j); diag(i, j); break; case 'B': diag(i, j); break; case 'N': horse(i, j); break; case 'K': king(i, j); break; } } int sol = -1; for (int i = 0; i < m; ++i) { dfs(i); if (bio.count() == m) { sol = i; break; } bio.reset(); steps.clear(); } if (sol == -1) { cout<<"NO\n"; return 0; } reverse(steps.begin(), steps.end()); for (const auto& step: steps) { cout<