求条CF1749E

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxN=4e5+5;
vector<string> grid;
vector<pair<int,int>> g[maxN];
int t,m,n,dx[]={0,0,1,-1},dy[]={1,-1,0,0},vis[maxN]={},dis[maxN]={},pre[maxN]={};
int encode(int x,int y){
	return x*m+y+1;
}
auto decode(int x){
	x--;
	return make_pair( x/m , x%m );
}
bool ingird(int x,int y){
	return 0<=x&&x<n&&0<=y&&y<m;
}
bool check(int x,int y){
	if(!ingird(x,y))
		return 0;
	for(int i=0;i<4;i++){
		int nx=x+dx[i],ny=y+dy[i];
		if(ingird(nx,ny)&&grid[nx][ny]=='#')
			return 0;
	}
	return 1;
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin>>t;
	while(t--){
		memset(dis,0x3f,sizeof(dis));
		cin>>n>>m;
		grid.resize(n);
		for(int i=0;i<n;i++)
			cin>>grid[i];
		auto add = [](int x,int y,int u){
			if(check(x,y))
				g[u].emplace_back(encode(x,y),grid[x][y]=='.');
		};
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				int u=encode(i,j);
				add(i-1,j+1,u);
				add(i+1,j+1,u);
				add(i-1,j-1,u);
				add(i+1,j-1,u);
			}
		}
		for(int i=0;i<n;i++)
			add(i,0,0);
		deque<int> dq={0};
		dis[0]=0;
		while(!dq.empty()){
			int u=dq.front();
			dq.pop_front();
			if(vis[u]++)
				continue;
			for(auto [v,w]:g[u]){
				if(dis[u]+w<dis[v]){
					dis[v]=dis[u]+w;
					pre[v]=u;
					if(w)
						dq.push_front(v);
					else
						dq.push_back(v);
				}
			}
		}
		int end=encode(0,m-1);
		for(int i=0;i<n;i++){
			int t=encode(i,m-1);
			if(dis[t]<dis[end])
				end=t;
		}
		if(dis[end]>=1e9)
			cout<<"NO"<<endl;
		else{
			cout<<"YES"<<endl;
			while(end){
				auto [x,y]=decode(end);
				grid[x][y]='#';
				end=pre[end];
			}
			for(int i=0;i<n;i++){
				for(int j=0;j<m;j++)
					cout<<grid[i][j];
				cout<<endl;
			}
		}
		for(int i=0;i<n;i++)
			grid[i].clear();
		for(int i=0;i<=n*m;i++)
			g[i].clear();
		memset(pre,0,sizeof(pre));
		memset(vis,0,sizeof(vis));
	}
	return 0;
}