This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub beet-aizu/library
// verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1613 #include <bits/stdc++.h> using namespace std; #define call_from_test #include "../../io/single.cpp" #include "../../tree/ahu.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); auto construct=[&](int h,int w){ auto st=read<string>(h); st.emplace(st.begin(),string(w,'.')); st.emplace(st.end(),string(w,'.')); for(auto &s:st) s='.'+s+'.'; h=st.size();w=st[0].size(); int dy[]={0,0,1,-1,1,1,-1,-1}; int dx[]={1,-1,0,0,1,-1,1,-1}; auto in=[&](int y,int x){return 0<=y and y<h and 0<=x and x<w;}; int n=0; vector blg(h,vector(w,-1)); auto bfs=[&](int y,int x){ int dir=(1+(st[y][x]=='#'))*4; using P = pair<int, int>; queue<P> que; auto push=[&](int ny,int nx){ if(~blg[ny][nx]) return; blg[ny][nx]=n; que.emplace(ny,nx); }; push(y,x); while(!que.empty()){ auto[cy,cx]=que.front();que.pop(); for(int k=0;k<dir;k++){ int ny=cy+dy[k],nx=cx+dx[k]; if(in(ny,nx) and st[cy][cx]==st[ny][nx]) push(ny,nx); } } n++; }; for(int i=0;i<h;i++) for(int j=0;j<w;j++) if(blg[i][j]<0) bfs(i,j); vector<set<int>> S(n); for(int i=0;i<h;i++){ for(int j=0;j<w;j++){ for(int k=0;k<4;k++){ int ni=i+dy[k],nj=j+dx[k]; if(in(ni,nj) and blg[i][j]!=blg[ni][nj]) S[blg[i][j]].emplace(blg[ni][nj]); } } } AHU G(n); for(int i=0;i<n;i++) for(int j:S[i]) if(i<j) G.add_edge(i,j); return G.build(); }; int h,w; while(cin>>h>>w,h||w){ auto T1=construct(h,w); cin>>h>>w; auto T2=construct(h,w); cout<<(T1==T2?"yes":"no")<<'\n'; } return 0; }
#line 1 "test/aoj/1613.test.cpp" // verification-helper: PROBLEM http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1613 #include <bits/stdc++.h> using namespace std; #define call_from_test #line 1 "io/single.cpp" #line 3 "io/single.cpp" using namespace std; #endif //BEGIN CUT HERE template<typename T=int> vector<T> read(size_t n){ vector<T> ts(n); for(size_t i=0;i<n;i++) cin>>ts[i]; return ts; } //END CUT HERE #ifndef call_from_test signed main(){ return 0; } #endif #line 1 "tree/ahu.cpp" #line 3 "tree/ahu.cpp" using namespace std; #endif // http://wwwmayr.in.tum.de/konferenzen/Jass08/courses/1/smal/Smal_Talk.pdf //BEGIN CUT HERE struct AHU{ inline static map<vector<int>, int> I; vector< vector<int> > G; AHU(int n):G(n){} void add_edge(int u,int v){ G[u].emplace_back(v); G[v].emplace_back(u); } int dfs(int v,int p){ vector<int> hs; for(int u:G[v]) if(u!=p) hs.emplace_back(dfs(u,v)); sort(hs.begin(),hs.end()); int sz=I.size(); if(!I.count(hs)) I[hs]=sz; return I[hs]; } int build(int r=0){ return dfs(r,-1); } }; //END CUT HERE #ifndef call_from_test //INSERT ABOVE HERE signed main(){ return 0; } #endif #line 9 "test/aoj/1613.test.cpp" #undef call_from_test signed main(){ cin.tie(0); ios::sync_with_stdio(0); auto construct=[&](int h,int w){ auto st=read<string>(h); st.emplace(st.begin(),string(w,'.')); st.emplace(st.end(),string(w,'.')); for(auto &s:st) s='.'+s+'.'; h=st.size();w=st[0].size(); int dy[]={0,0,1,-1,1,1,-1,-1}; int dx[]={1,-1,0,0,1,-1,1,-1}; auto in=[&](int y,int x){return 0<=y and y<h and 0<=x and x<w;}; int n=0; vector blg(h,vector(w,-1)); auto bfs=[&](int y,int x){ int dir=(1+(st[y][x]=='#'))*4; using P = pair<int, int>; queue<P> que; auto push=[&](int ny,int nx){ if(~blg[ny][nx]) return; blg[ny][nx]=n; que.emplace(ny,nx); }; push(y,x); while(!que.empty()){ auto[cy,cx]=que.front();que.pop(); for(int k=0;k<dir;k++){ int ny=cy+dy[k],nx=cx+dx[k]; if(in(ny,nx) and st[cy][cx]==st[ny][nx]) push(ny,nx); } } n++; }; for(int i=0;i<h;i++) for(int j=0;j<w;j++) if(blg[i][j]<0) bfs(i,j); vector<set<int>> S(n); for(int i=0;i<h;i++){ for(int j=0;j<w;j++){ for(int k=0;k<4;k++){ int ni=i+dy[k],nj=j+dx[k]; if(in(ni,nj) and blg[i][j]!=blg[ni][nj]) S[blg[i][j]].emplace(blg[ni][nj]); } } } AHU G(n); for(int i=0;i<n;i++) for(int j:S[i]) if(i<j) G.add_edge(i,j); return G.build(); }; int h,w; while(cin>>h>>w,h||w){ auto T1=construct(h,w); cin>>h>>w; auto T2=construct(h,w); cout<<(T1==T2?"yes":"no")<<'\n'; } return 0; }