题目要让我们求一个形似最小割的东西，肯定是转成对偶图上跑最短路解决。
首先把不合法的格子去掉，然后你从左边界走到右边界，只能走斜对角的格子，代价即为路径经过的 . 个数。
跑一遍 01 BFS，记录一下前驱状态以便构造。
#include<cstdio>
#include<algorithm>
#define N 400005
#define M 1600005
using namespace std;const int inf=0x3f3f3f3f;
const int dx[]={-1,1,0,0},dy[]={0,0,-1,1},Dx[]={-1,-1,1,1},Dy[]={-1,1,-1,1};
int T,n,m,d[N],pre[N];
int tot,head[N],nxt[M],ver[M],e[M];
int lt,rt,q[N*4];
char s[N],ss[N];
bool vis[N],ban[N];
int id(int x,int y) {return (x-1)*m+y;}
bool check(int x,int y) {return x>=1&&x<=n&&y>=1&&y<=m;
}
void insert(int x,int y,int z) {ver[++tot]=y,e[tot]=z,nxt[tot]=head[x],head[x]=tot;
}
int main() {scanf("%d",&T);XJX:while(T--) {tot=0;for(int i=1;i<=n*m;i++) {head[i]=vis[i]=ban[i]=pre[i]=0;}scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) {scanf("%s",ss+1);for(int j=1;j<=m;j++) {s[id(i,j)]=ss[j];if(s[id(i,j)]=='#') {for(int k=0;k<4;k++) {int x=i+dx[k],y=j+dy[k];if(check(x,y)) ban[id(x,y)]=1;}}}}for(int i=1;i<=n;i++) {for(int j=1;j<=m;j++) {if(ban[id(i,j)]) continue;for(int k=0;k<4;k++) {int x=i+Dx[k],y=j+Dy[k];if(check(x,y)&&!ban[id(x,y)]) insert(id(i,j),id(x,y),s[id(x,y)]=='.');}}}fill(d+1,d+n*m+1,inf);lt=N*2+1,rt=N*2;for(int i=1;i<=n;i++) {if(s[id(i,1)]=='.') d[id(i,1)]=1,q[++rt]=id(i,1);else d[id(i,1)]=0,q[--lt]=id(i,1);}while(lt<=rt) {int x=q[lt++]; vis[x]=1;for(int i=head[x];i;i=nxt[i]) {int y=ver[i],z=e[i];if(d[x]+z<d[y]) {d[y]=d[x]+z,pre[y]=x;if(z) q[++rt]=y; else q[--lt]=y;}}}int ans=inf,u=0;for(int i=1;i<=n;i++) {if(d[id(i,m)]<ans) ans=d[id(i,m)],u=id(i,m);}if(ans==inf) {puts("NO"); goto XJX;}while(u) s[u]='#',u=pre[u];puts("YES");for(int i=1;i<=n;i++) {for(int j=1;j<=m;j++) {putchar(s[id(i,j)]);}puts("");}}return 0;
}