题意
给一个 \(n\times m\) 的房间，有些位置是障碍。问能否在空地上画出若干条回路，使得每个空地恰好被经过一次。
\(n,m\le30\)。
思路
直接插头 \(DP\)？
不对，会 \(TLE\)。
考虑用网络流。如果每个空地的度都是 \(2\)，并且两条边不是连向同一个点，那么就是合法的。
用网络流刻画这个东西。
思路
// Problem: P3877 [TJOI2010] 打扫房间
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3877
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include<bits/stdc++.h>
using namespace std;
namespace IO{template<typename T>inline void read(T&x){x=0;char c=getchar();bool f=0;while(!isdigit(c)) c=='-'?f=1:0,c=getchar();while(isdigit(c)) x=x*10+c-'0',c=getchar();f?x=-x:0;}template<typename T>inline void write(T x){if(x==0){putchar('0');return ;}x<0?x=-x,putchar('-'):0;short st[50],top=0;while(x) st[++top]=x%10,x/=10;while(top) putchar(st[top--]+'0');}inline void read(char&c){c=getchar();while(isspace(c)) c=getchar();}inline void write(char c){putchar(c);}inline void read(string&s){s.clear();char c;read(c);while(!isspace(c)&&~c) s+=c,c=getchar();}inline void write(string s){for(int i=0,len=s.size();i<len;i++) putchar(s[i]);}template<typename T>inline void write(T*x){while(*x) putchar(*(x++));}template<typename T,typename...T2> inline void read(T&x,T2&...y){read(x),read(y...);}template<typename T,typename...T2> inline void write(const T x,const T2...y){write(x),putchar(' '),write(y...),sizeof...(y)==1?putchar('\n'):0;}
}using namespace IO;
const int maxn=50;
int n,m,fx[10]={0,0,0,1,-1},fy[10]={0,1,-1},bh[maxn][maxn];
char a[maxn][maxn];
namespace Network_Flow{const int inf=1000000000;template<int maxn,int maxm>class LSQXX{public:int head[maxn],nxt[maxm*2],to[maxm*2],val[maxm*2],cnt=1;void add(int u,int v,int w){nxt[++cnt]=head[u],to[cnt]=v,val[cnt]=w,head[u]=cnt;}void clear(){memset(head,0,sizeof(head));cnt=1;}};LSQXX<maxn*maxn,maxn*maxn*4>e;int s,t,d[maxn*maxn],cur[maxn*maxn];void edge_add(int u,int v,int w){e.add(u,v,w),e.add(v,u,0);}bool bfs(){for(int i=s;i<=t;i++) d[i]=inf;queue<int>q;q.push(s);d[s]=0;while(!q.empty()){int u=q.front();q.pop();for(int i=e.head[u];i;i=e.nxt[i]){int v=e.to[i];if(e.val[i]==0) continue;if(d[v]>d[u]+1) d[v]=d[u]+1,q.push(v);}}return d[t]!=inf;}int dfs(int u,int flow=inf){if(flow==0) return 0;if(u==t) return flow;int ans=0;for(int&i=cur[u];i;i=e.nxt[i]){int v=e.to[i];if(d[v]!=d[u]+1) continue;if(e.val[i]==0) continue;int new_flow=dfs(v,min(flow,e.val[i]));flow-=new_flow,ans+=new_flow;e.val[i]-=new_flow,e.val[i^1]+=new_flow;if(flow==0) return ans;}return ans;}void build(){e.clear();s=t=0;for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) bh[i][j]=++t;t++;for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){if(a[i][j]=='#') continue;if((i+j)&1) edge_add(bh[i][j],t,2);else{edge_add(s,bh[i][j],2);for(int f=1;f<=4;f++){int x=i+fx[f],y=j+fy[f];if(x<1||x>n||y<1||y>m) continue;if(a[x][y]=='#') continue;edge_add(bh[i][j],bh[x][y],1);}}}}int work(){int ans=0;while(bfs()){for(int i=s;i<=t;i++) cur[i]=e.head[i];ans+=dfs(s);}return ans;}
};
void solve(){read(n,m);for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) read(a[i][j]);int cnt_bl=0,cnt_wh=0;for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){if(a[i][j]=='#') continue;if((i+j)&1) cnt_bl++;else cnt_wh++;}if(cnt_bl!=cnt_wh){write("NO");return ;}Network_Flow::build();if(Network_Flow::work()==cnt_bl*2) write("YES");else write("NO");
}
signed main(){int T;read(T);while(T--) solve(),write("\n");return 0;
}