#include #include #include #include using namespace std; int N; char fig; struct Coor { int X, Y; Coor(int x, int y) : X(x), Y(y) {} Coor() {} bool operator==(Coor c) { return X == c.X && c.Y == Y; } }; struct Node { bool visited = false; bool removed = false; Coor coor; vector neighbours; //unordered_set ?? Node(const Coor &coor) : coor(coor) {} Node(int x, int y) { coor = Coor(x, y); } Node() {} bool friend operator>(const Node &th, const Node & other) { return th.neighbours.size() > other.neighbours.size(); } }; vector get_R_neighbours(Coor from) { vector result; for (int x = 1; x <= N; ++x) { if (x == from.X) continue; result.push_back(Coor(x, from.Y)); } for (int y = 1; y <= N; ++y) { if (y == from.Y) continue; result.push_back(Coor(from.X, y)); } return result; } vector get_B_neighbours(Coor from) { vector result; for (int i = 1; true; ++i) { Coor new_coor(from.X - i, from.Y - i); if (new_coor.X * new_coor.Y == 0) break; result.push_back(new_coor); } for (int i = 1; true; ++i) { Coor new_coor(from.X + i, from.Y + i); if (new_coor.X > N || new_coor.Y > N) break; result.push_back(new_coor); } for (int i = 1; true; ++i) { Coor new_coor(from.X + i, from.Y - i); if (new_coor.X > N || new_coor.Y == 0) break; result.push_back(new_coor); } for (int i = 1; true; ++i) { Coor new_coor(from.X - i, from.Y + i); if (new_coor.X == 0 || new_coor.Y > N) break; result.push_back(new_coor); } return result; } vector get_N_neighbours(Coor from) { vector pre_result, result; pre_result.push_back(Coor(from.X + 1, from.Y - 2)); pre_result.push_back(Coor(from.X - 1, from.Y - 2)); pre_result.push_back(Coor(from.X - 2, from.Y + 1)); pre_result.push_back(Coor(from.X - 2, from.Y - 1)); pre_result.push_back(Coor(from.X + 1, from.Y + 2)); pre_result.push_back(Coor(from.X - 1, from.Y + 2)); pre_result.push_back(Coor(from.X + 2, from.Y + 1)); pre_result.push_back(Coor(from.X + 2, from.Y - 1)); for (Coor c: pre_result) { if (c.X > 0 && c.X <= N && c.Y > 0 && c.Y <= N) { result.push_back(c); } } return result; } vector get_K_neighbours(Coor from) { vector pre_result, result; for (int x = from.X - 1; x <= from.X + 1; ++x) { for (int y = from.Y - 1; y <= from.Y + 1; ++y) { if (from.X == x && from.Y == y) continue; pre_result.push_back(Coor(x, y)); } } for (Coor c: pre_result) { if (c.X > 0 && c.X <= N && c.Y > 0 && c.Y <= N) { result.push_back(c); } } return result; } vector get_neighbours(Coor from) { switch (fig) { case 'R': return get_R_neighbours(from); case 'B': return get_B_neighbours(from); case 'N': return get_N_neighbours(from); case 'K': return get_K_neighbours(from); } } void solve_Qrtech(vector nodes) { //foreach nodes, print neighbours, nazdar cout << "YES" << endl; for (int i = 0; i < nodes.size() - 1; ++i) { Node last, current; last = nodes[i]; current = nodes[i + 1]; cout << last.coor.X << " " << last.coor.Y << " " << current.coor.X << " " << current.coor.Y << endl; } } bool compare(Node *n1, Node *n2) { return n1->neighbours.size() > n2->neighbours.size(); } int get_node_idx_with_min_neighbours(vector nodes) { bool is_null = true; int min_idx; int min_neigh_size; for(int idx = 0; idx < nodes.size(); idx++){ if(nodes[idx].removed) continue; if(is_null) { min_neigh_size = nodes[idx].neighbours.size(); min_idx = idx; is_null = false; } if(min_neigh_size > nodes[idx].neighbours.size()){ min_neigh_size = nodes[idx].neighbours.size(); min_idx = idx; } } return min_idx; } void problem() { cin >> N >> fig; vector nodes; nodes.reserve(N * N); vector> board(N + 1, vector(N + 1, nullptr)); for (int x = 1; x <= N; ++x) { string line; cin >> line; for (int y = 1; y <= N; ++y) { char ch = line[y - 1]; if (ch != '.') { nodes.push_back(Node(x, y)); board[x][y] = &nodes.back(); } } } if (fig == 'Q') { solve_Qrtech(nodes); return; } //find node neighbours for (int i = 0; i < nodes.size(); ++i) { Node *node = &(nodes[i]); //get neighbours vector neighbours_coors = get_neighbours(node->coor); for (Coor neigh_coor: neighbours_coors) { Node * neighbour = board[neigh_coor.X][neigh_coor.Y]; if(neighbour == nullptr) continue; node->neighbours.push_back(neighbour); } } //is it just one component ? vector> visited(N, vector(N, false)); queue queue; queue.push(&nodes[0]); int n_visited = 0; while (!queue.empty()) { Node *node = queue.front(); queue.pop(); if (node->visited) continue; node->visited = true; n_visited++; for (Node *neigh: node->neighbours) { if (!neigh->visited) { queue.push(neigh); } } } bool is_one_component = n_visited == nodes.size(); if (!is_one_component) { cout << "NO" << endl; return; } cout << "YES" << endl; Node *current, *next; int current_idx; for(int i = 0; i < nodes.size() - 1; ++i) { current_idx = get_node_idx_with_min_neighbours(nodes); current = &nodes[current_idx]; current->removed = true; next = current->neighbours[0]; cout << current->coor.X << " " << current->coor.Y << " " << next->coor.X << " " << next->coor.Y << " " << endl; for (Node* neighbour : current->neighbours) { for(int i = 0; i < neighbour->neighbours.size(); i++) { if(neighbour->neighbours[i] == current) { neighbour->neighbours.erase(neighbour->neighbours.begin() + i); break; } } } board[current->coor.X][current->coor.Y] = nullptr; } } int main() { problem(); return 0; }