#include #define REP(i,n) for(int i=0,i##_len=int(n);i > graph; vector< int > dist, match; vector< bool > used, vv; HopcroftKarp(int n, int m) : graph(n), match(m, -1), used(n) {} void add_edge(int u, int v) { graph[u].push_back(v); } void bfs() { dist.assign(graph.size(), -1); queue< int > que; for(int i = 0; i < graph.size(); i++) { if(!used[i]) { que.emplace(i); dist[i] = 0; } } while(!que.empty()) { int a = que.front(); que.pop(); for(auto &b : graph[a]) { int c = match[b]; if(c >= 0 && dist[c] == -1) { dist[c] = dist[a] + 1; que.emplace(c); } } } } bool dfs(int a) { vv[a] = true; for(auto &b : graph[a]) { int c = match[b]; if(c < 0 || (!vv[c] && dist[c] == dist[a] + 1 && dfs(c))) { match[b] = a; used[a] = true; return (true); } } return (false); } int bipartite_matching() { int ret = 0; while(true) { bfs(); vv.assign(graph.size(), false); int flow = 0; for(int i = 0; i < graph.size(); i++) { if(!used[i] && dfs(i)) ++flow; } if(flow == 0) return (ret); ret += flow; } } void output() { for(int i = 0; i < match.size(); i++) { if(~match[i]) { cout << match[i] << "-" << i << endl; } } } }; int main() { int h,w; cin>>h>>w; assert(h*w <= 100000); vector s(h); REP(i,h) cin>>s[i]; // 岩と穴に番号を付ける int X = 0, Y = 0; map, int> x, yw, yh; REP(i, h) REP(j, w) { if(s[i][j] == 'r'){ x[pair(i,j)] = X; X += 1; } if(s[i][j] == 'h') { yw[pair(j, i)] = Y; yh[pair(i, j)] = Y; Y += 1; } } HopcroftKarp G(X , Y); for (auto kvp: x) { // X(1~X) から Y(X+1~X+Y) への辺 pair pos = kvp.first; int node = kvp.second; auto iter = yw.lower_bound(pair(pos.second, pos.first)); if(iter != yw.end() && iter->first.first == pos.second) { G.add_edge(node, iter->second); } if(iter != yw.begin()) { iter = prev(iter); if(iter->first.first == pos.second) { G.add_edge(node, iter->second); } } iter = yh.lower_bound(pos); if(iter != yh.end() && iter->first.first == pos.first) { G.add_edge(node, iter->second); } if(iter != yh.begin()) { iter = prev(iter); if(iter->first.first == pos.first) { G.add_edge(node, iter->second); } } } cout << (G.bipartite_matching() == X?"Yes":"No") << endl; }