#include #include #include #include #include // #include #include #include #include using namespace std; #define ll long long #define FOR(i, L, R) for (int i = L; i < R; i++) #define pb push_back #define pii pair #define vi vector // #define int long long int /* ---------------------------------------------------------------------- */ ll N; // size char E; // excavator character char field[101][101]; // input vector> moves[255]; // moves for each piece type vector neighbours[10001]; //graph, possible movements foe each piece set kostra[10001]; int counter_kostra = 0; int E_indices[101][101]; pair E_positions[10001]; int index_counter = 0; /* ---------------------------------------------------------------------- */ tuple move(int x, int y, int c) { return tuple(x, y, c); } void add_move(char E, int x, int y, int c) { moves[(int)E].emplace_back(move(x, y, c)); } /* ---------------------------------------------------------------------- */ void add_neighbours(int i, int j) { for (auto &m : moves[E]) { int x = get<0>(m); int y = get<1>(m); int c = get<2>(m); int E_index = E_indices[i][j]; int i_n = i; int j_n = j; // cout << "\t" << get<0>(m) << " " << get<1>(m) << " " << get<2>(m) << " " << endl; while (c != 0) { i_n += x; j_n += y; int N_index = E_indices[i_n][j_n]; if (i_n >= 0 && i_n < N && j_n >= 0 && j_n < N) { if (field[i_n][j_n] == E) { // cout << "\t" << i_n << " " << j_n << " = " << E << endl; neighbours[E_index].emplace_back(N_index); } } else { // cout << "\t" << i_n << " " << j_n << " != " << E << endl; break; } c--; } } } /* ---------------------------------------------------------------------- */ void bfs(int i) { set visited; queue q; q.push(i); counter_kostra++; while (!q.empty()) { int current = q.front(); visited.insert(current); q.pop(); for (auto n : neighbours[current]) { if (visited.count(n) > 0) continue; q.push(n); visited.insert(n); kostra[current].insert(n); kostra[n].insert(current); counter_kostra++; // cout << current << "->" << n << endl; } } } /* ---------------------------------------------------------------------- */ void solve() { if (counter_kostra != index_counter) { cout << "NO" << endl; return; } cout << "YES" << endl; while (counter_kostra - 1) { for (int i = 0; i < index_counter; i++) { if (kostra[i].size() != 1) continue; int n = *kostra[i].begin(); cout << N - E_positions[i].first << " " << 1 + E_positions[i].second << " "; cout << N - E_positions[n].first << " " << 1 + E_positions[n].second; cout << endl; kostra[i].clear(); kostra[n].erase(i); counter_kostra--; } } } /* ---------------------------------------------------------------------- */ int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); /* ---------------------------------------------------------------------- */ cin >> N >> E; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { int i_r = N - 1 - i; cin >> field[i_r][j]; // cout << field[i_r][j] << " "; if (field[i_r][j] == E) { E_indices[i_r][j] = index_counter; E_positions[index_counter] = pair(i_r, j); index_counter++; } } // cout << endl; } // cout << "index_counter " << index_counter << endl; /* ---------------------------------------------------------------------- */ // King add_move('K', 1, 0, 1); // up add_move('K', -1, 0, 1); // down add_move('K', 0, -1, 1); // left add_move('K', 0, 1, 1); // right add_move('K', 1, -1, 1); // left up add_move('K', 1, 1, 1); // right up add_move('K', -1, -1, 1); // left down add_move('K', -1, 1, 1); // right down // Queen add_move('Q', 1, 0, -1); // up add_move('Q', -1, 0, -1); // down add_move('Q', 0, -1, -1); // left add_move('Q', 0, 1, -1); // right add_move('Q', 1, -1, -1); // left up add_move('Q', 1, 1, -1); // right up add_move('Q', -1, -1, -1); // left down add_move('Q', -1, 1, -1); // right down // Rook add_move('R', 1, 0, -1); // up add_move('R', -1, 0, -1); // down add_move('R', 0, -1, -1); // left add_move('R', 0, 1, -1); // right // Bishop add_move('B', 1, -1, -1); // left up add_move('B', 1, 1, -1); // right up add_move('B', -1, -1, -1); // left down add_move('B', -1, 1, -1); // right down // Horse add_move('N', 2, -1, 1); // up left add_move('N', 2, 1, 1); // up right add_move('N', -2, -1, 1); // down left add_move('N', -2, 1, 1); // down right add_move('N', 1, -2, 1); // left up add_move('N', -1, -2, 1); // left down add_move('N', 1, 2, 1); // right up add_move('N', -1, 2, 1); // right down /* ---------------------------------------------------------------------- */ // for (auto m : moves[E]) // { // cout << get<0>(m) << " " << get<1>(m) << " " << get<2>(m) << " " << endl; // } /* ---------------------------------------------------------------------- */ // create graph for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (field[i][j] == E) { // cout << i << " " << j << endl; add_neighbours(i, j); } } } // for (int i = 0; i < index_counter; i++) // { // cout << i << ": "; // for (auto x : neighbours[i]) // { // cout << x << " "; // } // cout << endl; // } // cout << "------------------------------------" << endl; bfs(0); // cout << counter_kostra << " " << index_counter << endl; // cout << "------------------------------------" << endl; // for (int i = 0; i < index_counter; i++) // { // cout << i << ": "; // for (auto x : kostra[i]) // { // cout << x << " "; // } // cout << endl; // } solve(); return 0; }