#include #include #include #include #include using namespace std; struct Coord { int x, y; bool operator != (const Coord & other) const { return (x!=other.x) || (y!=other.y); } }; struct Node { bool free = true, seen = false, desired = false; vector desiredCounterParts; // ty vole to je jak ten vytha my jsme uplni dementi }; void bfs(vector> & shore, Coord x) { int cntV = 0; int cntE = 0; if (shore[x.x][x.y].seen) return; if (!shore[x.x][x.y].free) return; queue q; q.push(x); while (!q.empty()) { cntV++; auto front = q.front(); q.pop(); for (auto & xxx : shore[front.x][front.y].desiredCounterParts) { cntE++; if (shore[xxx.x][xxx.y].seen || !shore[xxx.x][xxx.y].free) continue; q.push(xxx); } } if (cntE > cntV * 2) { cout << "No" << endl; exit(0); } } int main() { bool ans = true; int h, w, n; cin >> h >> w >> n; vector> shore(h, vector(w)); queue> q; map> dirDiff; dirDiff['D'] = { 0, -1}; dirDiff['U'] = { 0, 1}; dirDiff['L'] = {-1, 0}; dirDiff['R'] = { 1, 0}; for (int dock = 0; dock < n; ++dock) { int x, y, len; char dir; cin >> x >> y >> len >> dir; auto ddc = dirDiff[dir]; for (int i = 1; i < len-1; ++i) { Node &tile = shore[x + ddc.first*i][y + ddc.second*i]; // pls mr pc be a reference if (!tile.free) { cout << "No" << endl; return 0; } for (Coord & other: tile.desiredCounterParts) q.push({other, {x + ddc.first * i, y + ddc.second * i}}); tile.free = false; } Coord begCoord = {x, y}; Coord endCoord = {x + ddc.first * (len - 1), y + ddc.second * (len - 1)}; Node &beg = shore[x][y]; Node &end = shore[endCoord.x][endCoord.y]; beg.desired = end.desired = true; if (!shore[begCoord.x][begCoord.y].free && !shore[endCoord.x][endCoord.y].free) { cout << "No" << endl; return 0; } else if (!shore[begCoord.x][begCoord.y].free) { auto & tile = shore[endCoord.x][endCoord.y]; tile.free = false; for (Coord & other: tile.desiredCounterParts) q.push({other, {endCoord.x, endCoord.y}}); } else if (!shore[endCoord.x][endCoord.y].free) { auto &tile = shore[begCoord.x][begCoord.y]; tile.free = false; for (Coord & other: tile.desiredCounterParts) q.push({other, begCoord}); } else { beg.desiredCounterParts.push_back(endCoord); end.desiredCounterParts.push_back(begCoord); } while (!q.empty()) { auto & front = q.front(); q.pop(); auto & tile = shore[front.first.x][front.first.y]; if (!tile.free) { cout << "No" << endl; return 0; } tile.free = false; for (Coord & other: tile.desiredCounterParts) if (other != front.second) q.push({other, front.first}); } } for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { bfs(shore, {i, j}); } } return 0; }