#include #include #include struct Poz { Poz* r = this; int kolko = 0; int x = -1, y = -1; Poz(){} Poz(int x, int y) { this->x = x; this->y = y; } void setRoot(Poz* nr) { if (this == r) { r = nr; return; } r->setRoot(nr); r = nr; } Poz* getRoot() { if (this == r) { return this; } return r = r->getRoot(); } }; struct Hrana { Poz* a, *b; Hrana(Poz* x, Poz* y) { this->a = x; this->b = y; } }; int main() { char pole[100][100]; Poz pole2[100][100]; int size, pocet = 0; char znak; std::cin >> size; std::cin >> znak; for (size_t i = 0; i < size; i++) { for (size_t j = 0; j < size; j++) { std::cin >> pole[i][j]; } } std::vector h; int smery1[8][2]{ {0,1}, {1,1}, {0,-1}, {1,-1}, {-1,1}, {-1,0}, {-1,-1}, {1,0}}; int smery2[4][2]{ {0,1}, {0,-1}, {-1,0}, {1,0}}; int smery3[4][2]{ {-1,1}, {1,-1}, {-1,-1}, {1,1}}; int smery4[8][2]{ {2,1}, {1,2}, {2,-1}, {2,1}, {-1,2}, {1,2}, {-1,-2}, {1,-2} }; for (size_t i = 0; i < size; i++) { for (size_t j = 0; j < size; j++) { if (pole[i][j] != '.') { pole2[i][j].x = i; pole2[i][j].y = j; ++pocet; } } } for (size_t i = 0; i < size; i++) { for (size_t j = 0; j < size; j++) { if (pole2[i][j].x != -1) { if (znak == 'R') { for (size_t k = 0; k < 4; k++) { for (size_t l = 1; l < size; l++) { int ii = i + smery2[k][0] * l; int jj = j +smery2[k][1] *l ; if (ii < 0 || jj < 0 || ii >= size || jj >= size) { break; } if (pole[ii][jj] != '.') { h.push_back(Hrana(&pole2[i][j], &pole2[ii][jj])); break; } } } } else if (znak == 'Q') { for (size_t k = 0; k < 8; k++) { for (size_t l = 1; l < size; l++) { int ii = i + smery1[k][0] * l; int jj = j + smery1[k][1] * l; if (ii < 0 || jj < 0 || ii >= size || jj >= size) { break; } if (pole[ii][jj] != '.') { h.push_back(Hrana(&pole2[i][j], &pole2[ii][jj])); break; } } } } else if (znak == 'B') { for (size_t k = 0; k < 4; k++) { for (size_t l = 1; l < size; l++) { int ii = i + smery3[k][0] * l; int jj = j + smery3[k][1] * l; if (ii < 0 || jj < 0 || ii >= size || jj >= size) { break; } if (pole[ii][jj] != '.') { h.push_back(Hrana(&pole2[i][j], &pole2[ii][jj])); break; } } } } else if (znak == 'N') { for (size_t k = 0; k < 8; k++) { int ii = i + smery4[k][0]; int jj = j + smery4[k][1]; if (ii < 0 || jj < 0 || ii >= size || jj >= size) { break; } if (pole[ii][jj] != '.') { h.push_back(Hrana(&pole2[i][j], &pole2[ii][jj])); break; } } } else if (znak == 'K') { for (size_t k = 0; k < 8; k++) { int ii = i + smery1[k][0]; int jj = j + smery1[k][1]; if (ii < 0 || jj < 0 || ii >= size || jj >= size) { break; } if (pole[ii][jj] != '.') { h.push_back(Hrana(&pole2[i][j], &pole2[ii][jj])); break; } } } } } } std::vector kostra; for (size_t i = 0; i < h.size(); i++) { if (h[i].a->getRoot() != h[i].b->getRoot()) { h[i].a->setRoot(h[i].b->getRoot()); kostra.push_back(h[i]); if (pocet -1 == kostra.size()) { break; } } } bool da = kostra.size() == pocet -1; for (size_t i = 1; i < kostra.size(); i++) { if(kostra[0].a->getRoot() != kostra[i].a->getRoot()) { da = false; } kostra[0].a->kolko++; kostra[0].b->kolko++; } if (da) { std::sort(kostra.begin(), kostra.end(), [](Hrana& a, Hrana& b) { return std::min(a.a->kolko, a.b->kolko) < std::min(b.a->kolko, b.b->kolko); }); for (size_t i = 0; i < kostra.size(); i++) { if (kostra[i].a->kolko < kostra[i].b->kolko) { std::cout << (kostra[i].a->x + 1) << " " << (kostra[i].a->y + 1) << " " << (kostra[i].b->x + 1) << " " << (kostra[i].b->y + 1) << "\n"; kostra[i].a->x = kostra[i].b->x; kostra[i].a->y = kostra[i].b->y; } else { std::cout << (kostra[i].b->x + 1) << " " << (kostra[i].b->y + 1) << " " << (kostra[i].a->x + 1) << " " << (kostra[i].a->y + 1) << "\n"; kostra[i].b->x = kostra[i].a->x; kostra[i].b->y = kostra[i].a->y; } } } else { std::cout << "NO\n"; } return 0; }