#include // #include #define rng(a) a.begin(),a.end() #define rrng(a) a.rbegin(),a.rend() #define INF 2000000000000000000 #define ll long long #define ull unsigned long long #define ld long double #define pll pair using namespace std; templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b> G(MAX_V); vector level(MAX_V); vector iter(MAX_V); void add_edge(ll from, ll to, ll cap = 1) { G.at(from).push_back((edge){to, cap, (ll)G.at(to).size()}); G.at(to).push_back((edge){from, 0ll, (ll)G.at(from).size() - 1}); } void bfs(ll s) { for (ll i = 0; i < MAX_V; ++i) { level.at(i) = -1; } queue q; level.at(s) = 0; q.push(s); while (!q.empty()) { ll v = q.front(); q.pop(); for (ll i = 0; i < G.at(v).size(); ++i) { edge &e = G.at(v).at(i); if (e.cap > 0 && level.at(e.to) < 0) { level.at(e.to) = level.at(v) + 1; q.push(e.to); } } } } ll dfs(ll v, ll t, ll f) { if (v == t) { return f; } for (ll &i = iter.at(v); i < G.at(v).size(); ++i) { edge &e = G.at(v).at(i); if (e.cap > 0 && level.at(v) < level.at(e.to)) { ll d = dfs(e.to, t, min(f, e.cap)); if (d > 0) { e.cap -= d; G.at(e.to).at(e.rev).cap += d; return d; } } } return 0; } ll max_flow(ll s, ll t) { ll flow = 0; while (true) { bfs(s); if (level.at(t) < 0) { return flow; } for (ll i = 0; i < MAX_V; ++i) { iter.at(i) = 0; } ll f; while ((f = dfs(s, t, INF)) > 0) { flow += f; } } return flow; } //================================================= int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll H, W; cin >> H >> W; vector S(H); for (ll i = 0; i < H; ++i) { cin >> S.at(i); } ll rock = 0, hole = 0; for (ll i = 0; i < H; ++i) { for (ll j = 0; j < W; ++j) { if (S.at(i).at(j) == 'r') { rock += 1; } if (S.at(i).at(j) == 'h') { hole += 1; } } } ll s = H * W, t = s + 1; for (ll i = 0; i < H; ++i) { pll before_l = {-1, -1}; for (ll j = 0; j < W; ++j) { if (S.at(i).at(j) == 'h') { before_l = {i, j}; } if (S.at(i).at(j) == 'r') { if (before_l != (pll){-1, -1}) { add_edge(before_l.first * W + before_l.second, i * W + j); } } } pll before_r = {-1, -1}; for (ll j = W - 1; j >= 0; --j) { if (S.at(i).at(j) == 'h') { before_r = {i, j}; } if (S.at(i).at(j) == 'r') { if (before_r != (pll){-1, -1}) { add_edge(before_r.first * W + before_r.second, i * W + j); } } } } for (ll j = 0; j < W; ++j) { pll before_u = {-1, -1}; for (ll i = 0; i < H; ++i) { if (S.at(i).at(j) == 'h') { before_u = {i, j}; } if (S.at(i).at(j) == 'r') { if (before_u != (pll){-1, -1}) { add_edge(before_u.first * W + before_u.second, i * W + j); } } } pll before_d = {-1, -1}; for (ll i = H - 1; i >= 0; --i) { if (S.at(i).at(j) == 'h') { before_d = {i, j}; } if (S.at(i).at(j) == 'r') { if (before_d != (pll){-1, -1}) { add_edge(before_d.first * W + before_d.second, i * W + j); } } } } for (ll i = 0; i < H; ++i) { for (ll j = 0; j < W; ++j) { if (S.at(i).at(j) == 'h') { add_edge(s, i * W + j); } else if(S.at(i).at(j) == 'r') { add_edge(i * W + j, t); } } } if (max_flow(s, t) == rock) { cout << "Yes" << "\n"; } else { cout << "No" << "\n"; } }