#include using namespace std; const int INF = 1000000; template struct dinic{ struct edge{ int to, rev; Cap cap; edge(int to, int rev, Cap cap): to(to), rev(rev), cap(cap){ } }; int N; vector> G; dinic(){ } dinic(int N): N(N), G(N){ } void add_edge(int from, int to, Cap cap){ G[from].push_back(edge(to, G[to].size(), cap)); G[to].push_back(edge(from, G[from].size() - 1, 0)); } Cap dfs(vector &d, vector &iter, int v, int t, Cap f){ if (v == t){ return f; } while (iter[v] < G[v].size()){ int w = G[v][iter[v]].to; if (G[v][iter[v]].cap > 0 && d[v] < d[w]){ Cap f2 = dfs(d, iter, w, t, min(f, G[v][iter[v]].cap)); if (f2 > 0){ G[v][iter[v]].cap -= f2; G[w][G[v][iter[v]].rev].cap += f2; return f2; } } iter[v]++; } return 0; } Cap max_flow(int s, int t){ Cap flow = 0; while (true){ vector d(N, -1); d[s] = 0; queue Q; Q.push(s); while (!Q.empty()){ if (d[t] != -1){ break; } int v = Q.front(); Q.pop(); for (auto &e : G[v]){ int w = e.to; if (e.cap > 0 && d[w] == -1){ d[w] = d[v] + 1; Q.push(w); } } } if (d[t] == -1){ break; } vector iter(N, 0); while (true){ Cap f = dfs(d, iter, s, t, INF); if (f == 0){ break; } flow += f; } } return flow; } }; int main(){ int H, W; cin >> H >> W; vector> S(H, vector(W)); for (int i = 0; i < H; i++){ for (int j = 0; j < W; j++){ cin >> S[i][j]; } } vector> r, h; vector> id(H, vector(W)); for (int i = 0; i < H; i++){ for (int j = 0; j < W; j++){ if (S[i][j] == 'r'){ id[i][j] = r.size(); r.push_back(make_pair(i, j)); } if (S[i][j] == 'h'){ id[i][j] = h.size(); h.push_back(make_pair(i, j)); } } } int N = r.size(), M = h.size(); vector> st1(H), st2(W); for (int i = 0; i < H; i++){ for (int j = 0; j < W; j++){ if (S[i][j] == 'h'){ st1[i].insert(j); st2[j].insert(i); } } } dinic G(N + M + 2); for (int i = 0; i < N; i++){ G.add_edge(N + M, i, 1); } for (int i = 0; i < M; i++){ G.add_edge(N + i, N + M + 1, 1); } for (int i = 0; i < N; i++){ int x = r[i].first; int y = r[i].second; auto itr1 = st1[x].lower_bound(y); if (itr1 != st1[x].end()){ G.add_edge(i, N + id[x][*itr1], 1); } if (itr1 != st1[x].begin()){ G.add_edge(i, N + id[x][*prev(itr1)], 1); } auto itr2 = st2[y].lower_bound(x); if (itr2 != st2[y].end()){ G.add_edge(i, N + id[*itr2][y], 1); } if (itr2 != st2[y].begin()){ G.add_edge(i, N + id[*prev(itr2)][y], 1); } } int F = G.max_flow(N + M, N + M + 1); if (F == N){ cout << "Yes" << endl; } else { cout << "No" << endl; } }