#line 1 "Main.cpp" #include #include #include #include #include #line 2 "nachia\\array\\csr-array.hpp" #include #line 5 "nachia\\array\\csr-array.hpp" namespace nachia{ template class CsrArray{ public: struct ListRange{ using iterator = typename std::vector::iterator; iterator begi, endi; iterator begin() const { return begi; } iterator end() const { return endi; } int size() const { return (int)std::distance(begi, endi); } Elem& operator[](int i) const { return begi[i]; } }; struct ConstListRange{ using iterator = typename std::vector::const_iterator; iterator begi, endi; iterator begin() const { return begi; } iterator end() const { return endi; } int size() const { return (int)std::distance(begi, endi); } const Elem& operator[](int i) const { return begi[i]; } }; private: int m_n; std::vector m_list; std::vector m_pos; public: CsrArray() : m_n(0), m_list(), m_pos() {} static CsrArray Construct(int n, std::vector> items){ CsrArray res; res.m_n = n; std::vector buf(n+1, 0); for(auto& [u,v] : items){ ++buf[u]; } for(int i=1; i<=n; i++) buf[i] += buf[i-1]; res.m_list.resize(buf[n]); for(int i=(int)items.size()-1; i>=0; i--){ res.m_list[--buf[items[i].first]] = std::move(items[i].second); } res.m_pos = std::move(buf); return res; } static CsrArray FromRaw(std::vector list, std::vector pos){ CsrArray res; res.m_n = pos.size() - 1; res.m_list = std::move(list); res.m_pos = std::move(pos); return res; } ListRange operator[](int u) { return ListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; } ConstListRange operator[](int u) const { return ConstListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; } int size() const { return m_n; } int fullSize() const { return (int)m_list.size(); } }; } // namespace nachia #line 6 "nachia\\graph\\bipertite-matching.hpp" namespace nachia{ std::vector BipertiteMatching(int N1, int N2, const std::vector>& edges){ std::vector R(N2, -1); std::vector L(N1, -1); auto E = CsrArray::Construct(N1, edges); while(true){ std::vector bfs, dist(N1, -1), P(N1, -1); for(int i=0; i= maxD) break; for(int e : E[p]) if(L[p] != e){ if(R[e] >= 0){ if(dist[R[e]] < 0){ dist[R[e]] = dist[p] + 1; P[R[e]] = p; bfs.push_back(R[e]); } } else maxD = dist[p]; } } if(maxD > N1) break; std::vector I(N1, 0); for(int s=0; s= 0){ if(I[p] == E[p].size()){ p = P[p]; continue; } int q = E[p][I[p]++]; int r = R[q]; if(r == -1){ p2 = q; break; } if(dist[r] != dist[p] + 1) continue; P[r] = p; p = r; } if(p < 0) continue; while(p >= 0){ R[p2] = p; std::swap(L[p], p2); p = P[p]; } } } std::vector ans; for(int i=0; i<(int)edges.size(); i++){ auto& e = edges[i]; if(L[e.first] == e.second){ L[e.first] = -1; ans.push_back(i); } } return ans; } } // namespace nachia #line 7 "Main.cpp" using namespace std; using i32 = int; using u32 = unsigned int; using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(int i=0; i<(int)(n); i++) const i64 INF = 1001001001001001001; using Modint = atcoder::static_modint<998244353>; int main(){ int H,W; cin >> H >> W; vector G(H); rep(y,H) cin >> G[y]; vector> A; int numH = 0, numR = 0; vector> Id(H, vector(W)); rep(y,H) rep(x,W){ if(G[y][x] == 'h') Id[y][x] = numH++; if(G[y][x] == 'r') Id[y][x] = numR++; } rep(y,H){ int f = -1; rep(x,W){ if(G[y][x] == 'h') f = Id[y][x]; if(G[y][x] == 'r') if(f >= 0) A.emplace_back(f, Id[y][x]); } f = -1; for(int x=W-1; x>=0; x--){ if(G[y][x] == 'h') f = Id[y][x]; if(G[y][x] == 'r') if(f >= 0) A.emplace_back(f, Id[y][x]); } } rep(x,W){ int f = -1; rep(y,H){ if(G[y][x] == 'h') f = Id[y][x]; if(G[y][x] == 'r') if(f >= 0) A.emplace_back(f, Id[y][x]); } for(int y=H-1; y>=0; y--){ if(G[y][x] == 'h') f = Id[y][x]; if(G[y][x] == 'r') if(f >= 0) A.emplace_back(f, Id[y][x]); } } auto res = nachia::BipertiteMatching(numH, numR, A); int resnum = 0; for(auto a : res) if(a >= 0) resnum++; cout << (resnum == numR ? "Yes\n" : "No\n"); return 0; } struct ios_do_not_sync{ ios_do_not_sync(){ ios::sync_with_stdio(false); cin.tie(nullptr); } } ios_do_not_sync_instance;