//CERC 2020 - NCU1 - Excavation #include #include #include #include #include #include using namespace std; using t_type=char; using t_point=pair; enum Type { None = '.', Reepadlo = 'R', Qrtech = 'Q', Bugger = 'B', Namakatschenko = 'N', Kopatsch = 'K' }; struct Bool { Bool() : _val(false) {} Bool(bool val) : _val(val) {} bool operator !() { return !_val; } bool _val; }; vector> city; int n; t_type type; vector> res; unordered_map visited; #define E_IF(v1, v2) \ if (v1 >= 0 && v1 < n && v2 >= 0 && v2 < n) {\ if (city[v1][v2] == type) result.push_back({v1, v2});\ } vector getNeigb(const t_point &p) { vector result; if (type == Type::Reepadlo || type == Type::Qrtech) { for (int i = p.first - 1; i >= 0; --i) { if (city[i][p.second] == type) result.push_back({i, p.second}); } for (int i = p.first + 1; i < n; ++i) { if (city[i][p.second] == type) result.push_back({i, p.second}); } for (int i = p.second - 1; i >= 0; --i) { if (city[p.first][i] == type) result.push_back({p.first, i}); } for (int i = p.second + 1; i < n; ++i) { if (city[p.first][i] == type) result.push_back({p.first, i}); } } if (type == Type::Bugger || type == Type::Qrtech) { for (int i = p.first - 1, j = p.second - 1; i >= 0 && j >= 0; --i, --j) { if (city[i][j] == type) result.push_back({i, j}); } for (int i = p.first - 1, j = p.second + 1; i >= 0 && j < n; --i, ++j) { if (city[i][j] == type) result.push_back({i, j}); } for (int i = p.first + 1, j = p.second - 1; i < n && j >= 0; ++i, --j) { if (city[i][j] == type) result.push_back({i, j}); } for (int i = p.first + 1, j = p.second + 1; i < n && j < n; ++i, ++j) { if (city[i][j] == type) result.push_back({i, j}); } } if (type == Type::Kopatsch) { int i = p.first; int j = p.second; E_IF(i - 1, j - 1) E_IF(i + 1, j - 1) E_IF(i + 1, j + 1) E_IF(i - 1, j + 1) E_IF(i + 1, j) E_IF(i - 1, j) E_IF(i, j + 1) E_IF(i, j - 1) } if (type == Type::Namakatschenko) { int i = p.first; int j = p.second; E_IF(i + 2, j + 1) E_IF(i - 2, j + 1) E_IF(i + 2, j - 1) E_IF(i - 2, j - 1) E_IF(i + 1, j + 2) E_IF(i - 1, j + 2) E_IF(i + 1, j - 2) E_IF(i - 1, j - 2) } return result; } inline int h(const t_point &p){ return (p.first + 2) * (n + 2) + p.second; } void dfs(const t_point &p, const t_point &c) { visited[h(c)] = true; auto list = getNeigb(c); for (auto &p : list) { if (!visited[h(p)]) { dfs(c, p); } } res.push_back({c, p}); city[c.first][c.second] = Type::None; } void dfs(const t_point &p) { visited.clear(); dfs({-1, -1}, p); } t_point find(){ for (int i = 0; i < (int)city.size(); ++i) { for (int j = 0; j < (int)city[i].size(); ++j) { if (city[i][j] == type) { return {i, j}; } } } return {-1, -1}; } bool calc() { res.clear(); dfs(find()); int counter = 0; for (auto &v : city) { for (auto &t : v) { if (t == type) { ++counter; } } } return counter == 0; } int main() { cin >> n >> type; city = vector>(n, vector()); string line; getline(cin, line); for (int i = 0; i < n; ++i) { getline(cin, line); city[i] = vector(line.begin(), line.end()); } if (calc()) { cout << "YES\n"; for (auto &r : res) { if(r.second.first == -1) continue; cout << r.first.first + 1 << " " << r.first.second + 1 << " " << r.second.first + 1 << " " << r.second.second + 1 << "\n"; } } else { cout << "NO\n"; } return 0; }