#include #include #include #include #include using namespace std; int N; char type; vector> graph; vector> final_path; vector> positions; vector is_alive; vector> neighbours; 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()); for (int i = 0; i < N; ++i) { vector list; for(int j = i + 1; j(i, j)); ret = recursion(); if (ret) return ret; path.pop_back(); } } is_alive.at(i) = true; } } // printf("backtracking \n"); return false; } 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); // printf("init\n"); recursion(); // printf("recursion\n"); // for(auto p: final_path) // cout << "("<< get<0>(p) << " " << get<1>(p) << ") "; // printf("\n"); print_solution(); return 0; }