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