from sys import stdin
import heapq
def trace_path(i, j, visited, grid):
while j != 0:
grid[i][j] = '#'
i, j = visited[i][j]
grid[i][j] = '#'
for r in grid:
print("".join(r))
def solve():
n, m = map(int, stdin.readline().split())
grid = [list(stdin.readline().strip()) for i in range(n)]
visited = [[None] * m for i in range(n)]
for i in range(n):
for j in range(m):
if grid[i][j] == '#':
for di, dj in ((1, 0), (0, 1), (-1, 0), (0, -1)):
if 0 <= i + di < n and 0 <= j + dj < m:
visited[i+di][j+dj] = -1
q = [(1 if grid[i][0] == '.' else 0, i, 0) for i in range(n) if visited[i][0] != -1]
heapq.heapify(q)
while q:
c, i, j = heapq.heappop(q)
if j == m - 1:
print("YES")
trace_path(i, j, visited, grid)
return
for di, dj in ((-1, -1), (-1, 1), (1, -1), (1, 1)):
if 0 <= i + di < n and 0 <= j + dj < m \
and not visited[i+di][j+dj]:
visited[i+di][j+dj] = (i,j)
heapq.heappush(q, (c + (grid[i+di][j+dj] == '.'), i+di, j+dj))
print("NO")
for _ in range(int(stdin.readline())):
solve()#include <bits/stdc++.h>
using namespace std;
const long long MX=2e5+10;
const long long INF=1e18;
vector < long long > blc[MX];
vector < pair < long long , long long > > shl[MX];
vector < string > mas(MX);
long long corx[4]={1,1,-1,-1};
long long cory[4]={-1,1,1,-1};
priority_queue < pair < long long , pair < long long , long long > > > q;
long long n,m;
void BFS()
{
while(!q.empty())
{
long long zarx=q.top().second.first;
long long zary=q.top().second.second;
q.pop();
for(long long i=0;i<4;i++)
{
if(blc[zarx+corx[i]][zary+cory[i]]==-1)
{
continue;
}
if(blc[zarx+corx[i]][zary+cory[i]]==0 || (blc[zarx][zary]+(mas[zarx+corx[i]][zary+cory[i]]=='.'))<blc[zarx+corx[i]][zary+cory[i]])
{
blc[zarx+corx[i]][zary+cory[i]]=(blc[zarx][zary]+(mas[zarx+corx[i]][zary+cory[i]]=='.'));
shl[zarx+corx[i]][zary+cory[i]]=make_pair(zarx,zary);
q.push({-blc[zarx+corx[i]][zary+cory[i]],{zarx+corx[i],zary+cory[i]}});
}
}
}
return;
}
void fl()
{
for(long long i=0;i<=n+1;i++)
{
blc[i].resize(m+5);
shl[i].resize(m+5);
fill(blc[i].begin(),blc[i].end(),0);
fill(shl[i].begin(),shl[i].end(),make_pair(0,0));
blc[i][0]=-1;
blc[i][m+1]=-1;
}
fill(blc[0].begin(),blc[0].end(),-1);
fill(blc[n+1].begin(),blc[n+1].end(),-1);
return;
}
void fndshl()
{
long long zarx,zary;
long long abab=INF;
for(long long i=1;i<=n;i++)
{
if(blc[i][m]>0 && blc[i][m]<abab)
{
abab=blc[i][m];
zarx=i;
zary=m;
}
}
queue < pair < long long , long long > > nz;
while(zary!=1)
{
nz.push({zarx,zary});
long long newzarx=shl[zarx][zary].first;
long long newzary=shl[zarx][zary].second;
zarx=newzarx;
zary=newzary;
}
nz.push({zarx,zary});
while(!nz.empty())
{
mas[nz.front().first][nz.front().second]='#';
nz.pop();
}
cout<<"YES\n";
for(long long i=1;i<=n;i++)
{
for(long long j=1;j<=m;j++)
{
cout<<mas[i][j];
}
cout<<"\n";
}
return;
}
long long vipch()
{
fl();
for(long long i=1;i<=n;i++)
{
for(long long j=1;j<=m;j++)
{
if(((i+j)%2)==1 && mas[i][j]=='#')
{
blc[i-1][j]=-1;
blc[i][j-1]=-1;
blc[i+1][j]=-1;
blc[i][j+1]=-1;
}
}
}
for(long long i=1;i<=n;i+=2)
{
if(blc[i][1]==0)
{
blc[i][1]=1+(mas[i][1]=='.');
q.push({-blc[i][1],{i,1}});
}
}
BFS();
long long rt=INF;
for(long long i=1;i<=n;i++)
{
if(blc[i][m]>0)
{
rt=min(rt,blc[i][m]);
}
}
return rt;
}
long long vipb()
{
fl();
for(long long i=1;i<=n;i++)
{
for(long long j=1;j<=m;j++)
{
if(((i+j)%2)==0 && mas[i][j]=='#')
{
blc[i-1][j]=-1;
blc[i][j-1]=-1;
blc[i+1][j]=-1;
blc[i][j+1]=-1;
}
}
}
for(long long i=2;i<=n;i+=2)
{
if(blc[i][1]==0)
{
blc[i][1]=1+(mas[i][1]=='.');
q.push({-blc[i][1],{i,1}});
}
}
BFS();
long long rt=INF;
for(long long i=1;i<=n;i++)
{
if(blc[i][m]>0)
{
rt=min(rt,blc[i][m]);
}
}
return rt;
}
void fun()
{
cin>>n>>m;
string s;
for(long long i=1;i<=n;i++)
{
cin>>s;
s="&"+s+"&";
mas[i]=s;
}
long long mxansch=vipch();
long long mxansb=vipb();
//cout<<mxansch<<" "<<mxansb<<"\n";
if(mxansb==INF && mxansch==INF)
{
cout<<"NO\n";
return;
}
if(mxansch<mxansb)
{
vipch();
fndshl();
}
else
{
vipb();
fndshl();
}
return;
}
int main()
{
cin.tie(0);
ios_base::sync_with_stdio(0);
long long t;
cin>>t;
while(t--)
{
fun();
}
return 0;
}
237. Delete Node in a Linked List | 27. Remove Element |
39. Combination Sum | 378. Kth Smallest Element in a Sorted Matrix |
162. Find Peak Element | 1529A - Eshag Loves Big Arrays |
19. Remove Nth Node From End of List | 925. Long Pressed Name |
1051. Height Checker | 695. Max Area of Island |
402. Remove K Digits | 97. Interleaving String |
543. Diameter of Binary Tree | 124. Binary Tree Maximum Path Sum |
1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts | 501A - Contest |
160A- Twins | 752. Open the Lock |
1535A - Fair Playoff | 1538F - Interesting Function |
1920. Build Array from Permutation | 494. Target Sum |
797. All Paths From Source to Target | 1547B - Alphabetical Strings |
1550A - Find The Array | 118B - Present from Lena |
27A - Next Test | 785. Is Graph Bipartite |
90. Subsets II | 1560A - Dislike of Threes |