#include #include #include using namespace std; using ll=long long; #define all(v) v.begin(),v.end() #define rall(v) v.rbegin(),v.rend() template bool chmax(T &a, T b){if (a < b){a = b;return true;} else return false;} template bool chmin(T &a, T b){if (a > b){a = b;return true;} else return false;} struct UnionFind { private: vector par, siz; public: UnionFind(int n) : par(n, -1), siz(n, 1) {} int find(int x) { if (par[x] == -1) return x; else { par[x] = find(par[x]); return par[x]; } } bool same(int x, int y) { return find(x) == find(y); } int size(int x) { return siz[find(x)]; } bool merge(int x, int y) { x = find(x); y = find(y); if (x == y) return false; if (siz[x] < siz[y]) swap(x, y); siz[x] += siz[y]; par[y] = x; return true; } }; const int INF=1<<30; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int H,W; cin>>H>>W; vectorS(H); for(int i=0;i>S[i]; UnionFind uf1(H*W),uf2(H*W); for(int i=0;i=0&&S[i+1][j-1]=='#'){ uf2.merge(W*i+j,W*(i+1)+j-1); } } } } vectormin1(H*W,INF),max1(H*W,-INF),min2(H*W,INF),max2(H*W,-INF); for(int i=0;i(W)); for(int i=0;i>vp; for(int k=min1[l1];k<=max1[l1];k++){ flag1[k][j-i+k]=true; int l2=uf2.find(W*k+(j-i+k)); if(min2[l2]==INF)continue; int a=min(k-min2[l2],max2[l2]-k); if(min2[l2]!=max2[l2]){ vp.push_back(make_pair(k-a,k+a)); } } if(vp.empty()){ cout<<"No"<<"\n"; return 0; } sort(all(vp)); int l=vp[0].first,r=vp[0].second; vector>C; for(int k=1;k(W)); for(int i=0;i>vp; for(int k=min2[l2];k<=max2[l2];k++){ flag2[k][j+i-k]=true; int l1=uf1.find(W*k+(j+i-k)); if(min1[l1]==INF)continue; int a=min(k-min1[l1],max1[l1]-k); if(min1[l1]!=max1[l1]){ vp.push_back(make_pair(k-a,k+a)); } } sort(all(vp)); int l=vp[0].first,r=vp[0].second; vector>C; for(int k=1;k