我说老实话真感觉这题没有紫

传送门

解法

我们把第 $n+1$ 行看成一整个物体，一个物体会停下来当且仅当它与另一个物体有了上下接触，不难想到碰到的那个物体一定是某一列上离它最近的那个。

现在的问题是如何算出来，可以考虑图论建模。先 bfs 一遍给每个物体编号，然后对于第 $i$ 个物体找到同一列下方离它最近的物体 $j$，从 $j$ 向 $i$ 连一条边权为行数之差的边。

我实现的方法是把第 $n+1$ 行编号为 $0$，然后就只用以 $0$ 为源点跑一遍最短路，求出来的 $dis_i$ 就是第 $i$ 个物体会下落的行数。直接交换然后输出即可。

更具体的细节可以看代码。

#include<bits/stdc++.h>
using namespace std;
typedef long long lo;
#ifdef __linux__
#define gc getchar_unlocked
#define pc putchar_unlocked
#else
#define gc _getchar_nolock
#define pc _putchar_nolock
#endif
inline bool blank(const char x){return !(x^32)||!(x^10)||!(x^13)||!(x^9);}
template<typename Tp> inline void read(Tp&x){x=0;register bool z=true;register char a=gc();for(;!isdigit(a);a=gc())if(a=='-')z=false;for(;isdigit(a);a=gc())x=(x<<1)+(x<<3)+(a^48);x=(z?x:~x+1);}
inline void read(double&x){x=0.0;register bool z=true;register double y=0.1;register char a=gc();for(;!isdigit(a);a=gc())if(a=='-')z=false;for(;isdigit(a);a=gc())x=x*10+(a^48);if(a!='.')return x=z?x:-x,void();for(a=gc();isdigit(a);a=gc(),y/=10)x+=y*(a^48);x=(z?x:-x);}
inline void read(char&x){for(x=gc();blank(x)&&(x^-1);x=gc());}
inline void read(char *x){register char a=gc();for(;blank(a)&&(a^-1);a=gc());for(;!blank(a)&&(a^-1);a=gc())*x++=a;*x=0;}
inline void read(string&x){x="";register char a=gc();for(;blank(a)&&(a^-1);a=gc());for(;!blank(a)&&(a^-1);a=gc())x+=a;}
template<typename T,typename...Tp> inline void read(T&x,Tp&...y){read(x),read(y...);}
template<typename Tp> inline void write(Tp x){if(!x)return pc(48),void();if(x<0)pc('-'),x=~x+1;register int len=0;register char tmp[64];for(;x;x/=10)tmp[++len]=x%10+48;while(len)pc(tmp[len--]);}
inline void write(const double x){register int a=6;register double b=x,c=b;if(b<0)pc('-'),b=-b,c=-c;register double y=5*powl(10,-a-1);b+=y,c+=y;register int len=0;register char tmp[64];if(b<1)pc(48);else for(;b>=1;b/=10)tmp[++len]=floor(b)-floor(b/10)*10+48;while(len)pc(tmp[len--]);pc('.');for(c*=10;a;a--,c*=10)pc(floor(c)-floor(c/10)*10+48);}
inline void write(const pair<int,double>x){register int a=x.first;if(a<7){register double b=x.second,c=b;if(b<0)pc('-'),b=-b,c=-c;register double y=5*powl(10,-a-1);b+=y,c+=y;register int len=0;register char tmp[64];if(b<1)pc(48);else for(;b>=1;b/=10)tmp[++len]=floor(b)-floor(b/10)*10+48;while(len)pc(tmp[len--]);a&&(pc('.'));for(c*=10;a;a--,c*=10)pc(floor(c)-floor(c/10)*10+48);} else cout<<fixed<<setprecision(a)<<x.second;}
inline void write(const char x){pc(x);}
inline void write(const bool x){pc(x?49:48);}
inline void write(char *x){fputs(x,stdout);}
inline void write(const char *x){fputs(x,stdout);}
inline void write(const string&x){fputs(x.c_str(),stdout);}
template<typename T,typename...Tp> inline void write(T x,Tp...y){write(x),write(y...);}
const int N=1e6+5;
typedef pair<lo,lo> pll;
bool B;
string s[N];
idxctor<lo>idx[N];
idxctor<pll>g[N];
lo n,m,dx[]={1,-1,0,0},dy[]={0,0,1,-1},cnt,dis[N];
void bfs(lo i,lo j)
{
  queue<pll>q;q.emplace(i,j);
  while(q.size())
  {
    auto[x,y]=q.front();q.pop();
    if(idx[x][y])continue;
    idx[x][y]=cnt;
    for(lo k=0;k<4;k++)
    {
      lo xx=x+dx[k],yy=y+dy[k];
      if(xx<=n&&xx>=1&&yy<=m&&yy>=1&&s[xx][yy-1]=='#')q.emplace(xx,yy);
    }
  }
}
bitset<N>vis;
bool E;
void dij()
{
  priority_queue<pll,idxctor<pll>,greater<pll>>q;
  for(lo i=1;i<=cnt;i++)dis[i]=1e18;
  q.emplace(dis[0]=0,0);vis.reset();
  while(q.size())
  {
    lo u=q.top().second;q.pop();
    if(vis.test(u))continue;
    vis.set(u);
    for(auto[v,w]:g[u])if(dis[v]>dis[u]+w)q.emplace(dis[v]=dis[u]+w,v);
  }
}
int main()
{
  read(n,m);
  idx[0].resize(m+1);idx[n+1].resize(m+1);
  for(lo i=1;i<=n;i++)read(s[i]),idx[i].resize(m+1);
  for(lo i=1;i<=n;i++)for(lo j=1;j<=m;j++)if(s[i][j-1]=='#'&&!idx[i][j])cnt++,bfs(i,j);
  for(lo j=1;j<=m;j++)
  {
    lo ls=n+1;
    for(lo i=n;i>0;i--)if(idx[i][j])
    {
      g[idx[ls][j]].emplace_back(idx[i][j],ls-i-1);
      ls=i;while(idx[ls][j]==idx[i][j]&&ls>0)ls--;
      i=ls++;
    }
  }
  dij();
  for(lo j=1;j<=m;j++)for(lo i=n;i;i--)if(idx[i][j])swap(s[i][j-1],s[i+dis[idx[i][j]]][j-1]);
  for(lo i=1;i<=n;i++)write(s[i],'\n');
}

复杂度其实有点劣，毕竟带了个 $\log$。