#include #define REP(i,n) for(int i=0,i##_len=int(n);i struct Edge { int rev, from, to; // rev:逆向きの辺の番号 T cap, original_cap; Edge(int r, int f, int t, T c) : rev(r), from(f), to(t), cap(c), original_cap(c) {} }; template struct Graph { vector>> G; Graph(int n = 0) : G(n) {} vector>& operator[](int i) { return G[i]; } const size_t size() const { return G.size(); } Edge& redge(Edge e) { // 逆向きの辺を返す return G[e.to][e.rev]; // 自己ループはないと仮定(あれば G[e.to][e.rev + 1] とする必要がある) } void add_edge(int from, int to, T cap) { // 有向辺を加える G[from].push_back(Edge((int)G[to].size(), from, to, cap)); G[to].push_back(Edge((int)G[from].size() - 1, to, from, 0)); } }; /* FordFulkerson: Ford-Fulkersonのアルゴリズムで最大流を求める構造体 max_flow(G,s,t) :グラフGの最大流が求まる 副作用:G は最大流の残余ネットワークになる 計算量: O(|f*||E|) (f*:最大流) */ template struct FordFulkerson { const T INF = 1e9; vector used; FordFulkerson(){}; T dfs(Graph& G, int v, int t, T f) { // 増加可能経路を見つけて増加分のフローを返す if (v == t) return f; used[v] = true; for (auto& e : G[v]) { if (!used[e.to] && e.cap > 0) { T d = dfs(G, e.to, t, min(f, e.cap)); if (d > 0) { e.cap -= d; G.redge(e).cap += d; return d; } } } return 0; } T max_flow(Graph& G, int s, int t) { T flow = 0; while (true) { used.assign(G.size(), 0); T f = dfs(G, s, t, INF); // f が増加分のフロー if (f == 0) { return flow; } else { flow += f; } } return 0; } }; 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, E; 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; } } Graph G(X + Y + 2); for (int i = 0; i < X; i++) { // ソース(0)から X(1~X) への辺 G.add_edge(0, i + 1, 1); } 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 + 1, iter->second + X + 1, 1); } if(iter != yw.begin()) { iter = prev(iter); if(iter->first.first == pos.second) { G.add_edge(node + 1, iter->second + X + 1, 1); } } iter = yh.lower_bound(pos); if(iter != yh.end() && iter->first.first == pos.first) { G.add_edge(node + 1, iter->second + X + 1, 1); } if(iter != yh.begin()) { iter = prev(iter); if(iter->first.first == pos.first) { G.add_edge(node + 1, iter->second + X + 1, 1); } } } for (int i = 0; i < Y; i++) { // Y(X+1~X+Y) からシンク(X+Y+1)への辺 G.add_edge(i + X + 1, X + Y + 1, 1); } FordFulkerson ff; cout << (ff.max_flow(G, 0, X + Y + 1) == X?"Yes":"No") << endl; }