#include #include #include //3 R //R.. //R.. //..R using namespace std; struct Excavator { int x; int y; Excavator(int x, int y) : x(x), y(y) { } // Checking if game is finished. static bool onlyOneExcavatorLeft(vector>& city) { int number = 0; for (int i = 0; i < city.size(); i++) { for (int j = 0; j < city[i].size(); j++) { if (city[i][j] != nullptr) { number++; } } } if (number == 1) { return true; } else { return false; } } // Moving the excavator. (ticking) bool move(vector>& city) { for (int i = 0; i < city.size(); i++) { for (int j = 0; j < city[i].size(); j++) { // find a non empty field which is not itself and if (city[i][j] != nullptr) { if (canHitDirectly(i, j)) { moveTo(city, i, j); } else { moveCloserTo(city, i, j); } } } } return true; } // Checking if able to hit a spot. bool canHitAll(vector>& city) { for (int i = 0; i < city.size(); i++) { for (int j = 0; j < city[i].size(); j++) { if (city[i][j] != nullptr) { if (canHit(city, i, j)) { continue; } else { return false; } } } } return true; } // Checking if can hit directly a spot. virtual bool canHitDirectly(int x, int y) = 0; virtual bool canHit(vector>& city, int x, int y) = 0; // Moving closer to a spot, in order to be able to directly hit it. virtual void moveCloserTo(vector>& city, int x, int y) = 0; // Moving to a spot. void moveTo(vector>& city, int x, int y) { city[this->x][this->y] = nullptr; city[x][y] = this; cout << this->x + 1 << " " << this->y + 1 << " " << x + 1 << " " << y + 1 << endl; this->x = x; this->y = y; } }; struct Reepadlo : Excavator { Reepadlo(int x, int y) : Excavator(x, y) { } bool canHit(vector>& city, int x, int y) override { if (x == this->x && y == this->y) { return false; } return true; } bool canHitDirectly(int x, int y) override { return (x == this->x || y == this->y) && !(x == this->x && y == this->y); } void moveCloserTo(vector>& city, int x, int y) override { Excavator::moveTo(city, this->x, y); } }; struct Qrtech : Excavator { Qrtech(int x, int y) : Excavator(x, y) { } bool canHit(vector>& city, int x, int y) override { return true; } bool canHitDirectly(int x, int y) override { if (x == this->x && y == this->y) { return false; } return (x == this->x || y == this->y); } void moveCloserTo(vector>& city, int x, int y) override { Excavator::moveTo(city, this->x, y); } }; struct Kopatsch : Excavator { Kopatsch(int x, int y) : Excavator(x, y) { } bool canHit(vector>& city, int x, int y) override { return true; } bool canHitDirectly(int x, int y) override { if (x == this->x && y == this->y) { return false; } return abs(x - this->x) <= 1 && abs(y - this->y) <= 1; } void moveCloserTo(vector>& city, int x, int y) override { int finalX = this->x; int finalY = this->y; if (this->y > y) { finalY--; } else if (this->y < y) { finalY++; } if (this->x > x) { finalX--; } else if (this->x < x) { finalX++; } Excavator::moveTo(city, finalX, finalY); } }; struct Namakatschenko : Excavator { Namakatschenko(int x, int y) : Excavator(x, y) { } bool canHit(vector>& city, int x, int y) override { if (city.size() == 3) { if (x == 1 && y == 1) { return false; } else { return true; } } if (city.size() > 3) return true; if (city.size() < 3) return false; } bool canHitDirectly(int x, int y) override { if (x == this->x && y == this->y) { return false; } if (this->x + 2 == x && this->y + 1 == y) return true; if (this->x + 2 == x && this->y - 1 == y) return true; if (this->x - 2 == x && this->y + 1 == y) return true; if (this->x - 2 == x && this->y - 1 == y) return true; if (this->x + 1 == x && this->y + 2 == y) return true; if (this->x + 1 == x && this->y - 2 == y) return true; if (this->x - 1 == x && this->y + 2 == y) return true; if (this->x - 1 == x && this->y - 2 == y) return true; return false; } void moveCloserTo(vector>& city, int x, int y) override { int deltaX = x - this->x; int deltaY = x - this->y; // if not in proximity (not in length of 2) int finalX = this->x; int finalY = this->y; if (abs(deltaX) > 2) { if (deltaX > 0) { finalX += 2; } else { finalX -= 2; } if (deltaY > 0) { finalY += 1; } else { finalY -= 1; } } else if (abs(deltaY) > 2) { if (deltaY > 0) { finalX += 2; } else { finalX -= 2; } if (deltaX > 0) { finalY += 1; } else { finalY -= 1; } } // 1 step if (deltaX == 2 && deltaY == 1) { finalX = this->x + 2; finalY = this->y + 1; } if (deltaX == -2 && deltaY == 1) { finalX = this->x - 2; finalY = this->y + 1; } if (deltaX == 2 && deltaY == -1) { finalX = this->x + 2; finalY = this->y - 1; } if (deltaX == -2 && deltaY == -1) { finalX = this->x - 2; finalY = this->y - 1; } if (deltaX == 1 && deltaY == 2) { finalX = this->x + 1; finalY = this->y + 2; } if (deltaX == -1 && deltaY == 2) { finalX = this->x - 1; finalY = this->y + 2; moveTo(city, this->x - 1, this->y + 2); } if (deltaX == 1 && deltaY == -2) { finalX = this->x + 1; finalY = this->y - 2; } if (deltaX == -1 && deltaY == -2) { finalX = this->x - 1; finalY = this->y - 2; } // 2 step if (deltaX == 0 && deltaY == 2) { if (this->x + 2 < city.size()) { finalX = this->x + 2; finalY = this->y + 1; } else { finalX = this->x - 2; finalY = this->y + 1; } } if (deltaX == 0 && deltaY == -2) { if (this->y + 2 < city.size()) { finalX = this->x + 2; finalY = this->y - 1; } else { finalX = this->x - 2; finalY = this->y - 1; } } if (deltaX == 2 && deltaY == 0) { if (this->y + 2 < city.size()) { finalX = this->x + 1; finalY = this->y + 2; } else { finalX = this->x + 1; finalY = this->y - 2; } } if (deltaX == -2 && deltaY == 0) { if (this->y + 2 < city.size()) { finalX = this->x - 1; finalY = this->y + 2; } else { finalX = this->x - 1; finalY = this->y - 2; } } if (deltaX == 1 && deltaY == 1) { if (this->x + 2 < city.size()) { finalX = this->x + 2; finalY = this->y - 1; } else { finalX = this->x - 1; finalY = this->y + 2; } } if (deltaX == 1 && deltaY == -1) { if (this->y + 2 < city.size()) { finalX = this->x - 1; finalY = this->y + 2; } else { finalX = this->x + 2; finalY = this->y - 1; } } if (deltaX == -1 && deltaY == -1) { if (this->y + 2 < city.size()) { finalX = this->x - 2; finalY = this->y + 1; moveTo(city, this->x - 2, this->y + 1); } else { finalX = this->x - 1; finalY = this->y + 2; } } if (deltaX == -1 && deltaY == 1) { if (this->y + 2 < city.size()) { finalX = this->x + 1; finalY = this->y + 2; } else { finalX = this->x - 1; finalY = this->y - 2; } } // 3 steps if (deltaX == 1 && deltaY == 0) { if (this->y + 2 < city.size()) { finalX = this->x + 1; finalY = this->y + 2; } else { finalX = this->x - 2; finalY = this->y - 1; } } if ((finalX == this->x && finalY == this->y)) { if (deltaY > 0) { finalY += 1; } else { finalY -=1; } if (deltaX > 0) { finalX += 2; } else { finalX -= 2; } } moveTo(city, finalX, finalY); } }; struct Bugger : Excavator { Bugger(int x, int y) : Excavator(x, y) { } bool canHit(vector>& city, int x, int y) override { return (this->x + this->y) % 2 == (x + y) % 2; } bool canHitDirectly(int x, int y) override { if (x == this->x && y == this->y) { return false; } int deltaX = x - this->x; int deltaY = y - this->y; return abs(deltaX) == abs(deltaY); } void moveCloserTo(vector>& city, int x, int y) override { vector> fields(city.size(), vector(city.size(), 0)); for (int i = 0; i < fields.size(); i++) { // given position if (x + i < fields.size() && y + i < fields.size()) { fields[x + i][y + i]++; } if (x + i < fields.size() && y - i >= 0) { fields[x + i][y - i]++; } if (x - i >= 0 && y + i < fields.size()) { fields[x - i][y + i]++; } if (x - i >= 0 && y - i >= 0) { fields[x - i][y - i]++; } // this if (this->x + i < fields.size() && this->y + i < fields.size()) { fields[this->x + i][this->y + i]++; } if (this->x + i < fields.size() && this->y - i >= 0) { fields[this->x + i][this->y - i]++; } if (this->x - i >= 0 && this->y + i < fields.size()) { fields[this->x - i][this->y + i]++; } if (this->x - i >= 0 && this->y - i >= 0) { fields[this->x - i][this->y - i]++; } } for (int i = 0; i < fields.size(); i++) { for (int j = 0; j < fields.size(); j++) { if (fields[i][j] == 2) { moveTo(city, i, j); return; } } } } }; void solve() { int N; cin >> N; char excavatorType; cin >> excavatorType; vector> city(N, vector(N, nullptr)); Excavator* excavator; // Updating the field for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { char field; cin >> field; switch (field) { case 'R' : { city[i][j] = new Reepadlo(i, j); } case 'B' : { city[i][j] = new Bugger(i, j); } case 'Q' : { city[i][j] = new Qrtech(i, j); } case 'K' : { city[i][j] = new Kopatsch(i, j); } case 'N' : { city[i][j] = new Namakatschenko(i, j); } default: { } } if (city[i][j] != nullptr) { excavator = city[i][j]; } } } if (excavator->canHitAll(city)) { cout << "YES" << endl; int tries = 0; while (!Excavator::onlyOneExcavatorLeft(city) || tries > 100000) { excavator->move(city); tries++; } } else { cout << "NO" << endl; } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); solve(); return 0; }