#include #include #include #include #include #include #include using namespace std; int N; char type; queue q; vector> graph; vector> final_path; vector> positions; vector is_alive; vector> neighbours; vector> skeleton; vector> path; void print_solution() { if (final_path.size() == N - 1) { printf("YES\n"); for (tuple a: final_path) { printf("%d %d %d %d\n", get<0>(positions.at(get<0>(a))), get<1>(positions.at(get<0>(a))), get<0>(positions.at(get<1>(a))), get<1>(positions.at(get<1>(a)))); } } else { printf("NO\n"); } } bool is_reachable(tuple a, tuple b) { bool ret; switch (type) { case 'R': ret = get<0>(a) == get<0>(b) || get<1>(a) == get<1>(b); break; case 'Q': // horizontal lines ret = abs(get<0>(a) - get<0>(b)) == abs(get<1>(a) - get<1>(b)) || get<0>(a) == get<0>(b) || get<1>(a) == get<1>(b); break; case 'B': ret = abs(get<0>(a) - get<0>(b)) == abs(get<1>(a) - get<1>(b)); break; case 'K': ret = abs(get<0>(a) - get<0>(b)) <= 1 && abs(get<1>(a) - get<1>(b)) <= 1; break; default: ret = (abs(get<0>(a) - get<0>(b)) == 2 && abs(get<1>(a) - get<1>(b)) == 1) || (abs(get<0>(a) - get<0>(b)) == 1 && abs(get<1>(a) - get<1>(b)) == 2); } return ret; } bool get_graph(const vector> &nodes) { neighbours.reserve(N); for (int i = 0; i < N; ++i) { neighbours.emplace_back(vector()); skeleton.emplace_back(vector()); } for (int i = 0; i < N; ++i) { vector list; for (int j = i + 1; j < N; ++j) { if (is_reachable(nodes.at(i), nodes.at(j))) { neighbours.at(j).push_back(i); neighbours.at(i).push_back(j); } } } for (int i = 0; i < N; ++i) { if (neighbours.at(i).empty()) { print_solution(); return false; } } return true; } void print_skeleton(vector> a) { for (int i = 0; i < a.size(); i++) { printf("%d:\t", i); for (int x: a.at(i)) printf("%d ", x); printf("\n"); } } int main() { char c; scanf("%d %c\n", &N, &type); for (int i = 1; i <= N; ++i) { for (int j = 1; j <= N; ++j) { scanf("%c", &c); if (c != '.') positions.emplace_back(i, j); } scanf("%c", &c); } N = positions.size(); // for (tuple a: positions) // printf("%d %d\n", get<0>(a), get<1>(a)); // printf("N %d\n", N); if (!get_graph(positions)) return 0; is_alive.reserve(N); for (int i = 0; i < N; ++i) { is_alive.emplace_back(true); } is_alive.at(0) = false; int cur; q.push(0); while (!q.empty()) { cur = q.front(); q.pop(); for (int to: neighbours.at(cur)) { if (is_alive.at(to)) { is_alive.at(to) = false; skeleton.at(cur).emplace_back(to); skeleton.at(to).emplace_back(cur); q.push(to); } } } // print_skeleton(skeleton); for (bool alive: is_alive) if (alive) { print_solution(); return 0; } for (int i = N; i > 1;) { for (int j = 0; j < N; ++j) { if (skeleton.at(j).size() == 1) { final_path.emplace_back(j, skeleton.at(j).at(0)); int neighbour_id = skeleton.at(j).at(0); for (int k = 0; k < skeleton.at(neighbour_id).size(); ++k) { if (skeleton.at(neighbour_id).at(k) == j) { skeleton.at(neighbour_id).erase(skeleton.at(neighbour_id).begin() + k); } } remove(skeleton.at(j).begin(), skeleton.at(j).end(), j); --i; skeleton.at(j).pop_back(); break; } } // print_skeleton(skeleton); } // for (tuple t: final_path) { // printf("(%d %d) ", get<0>(t), get<1>(t)); // } // printf("\n"); print_solution(); return 0; }