首先整理一下条件：

1、恰好进出每个需打扫的房间各一次

2、进出每个房间不能通过同一个门

（其实前两个条件是一回事）

3、要求每条路线都是一个闭合的环线

4、每条路线经过的房间数大于2

让你在一个n*m的矩阵中，找出是否能按照约定方案打扫全部指定房间。

首先不难得出一个结论：有奇数个需要打扫的房间时一定无解。

证明？

每一次打扫都要满足条件3和4，而闭合的环线为多边形，显然必须对称（即通过平移可得到矩形），不难看出：每一次都能且只能打扫偶数个房间。

然后稍作分析，发现每个格子的度为2（即进入此房再出去）。

考虑建图。

一个房间上下左右有门，我们自然而然想到一个点向周围四个连边，就构成了黑白染色的模型。

一个矩阵中的房间最多用两条路线打扫即可。

每个点都要走到。

所以每个点都会向上下左右异色格点流出1，同时也会接受另一个点的流入。

我们这时将白点流向黑点的流反向，这样每个白点流入2，每个黑点流出2。

于是每个点有2的流量，来说明可以有两条边和它相连。

黑点都向S连边，白点都向T连边

然后图建好了，开始跑网络流，如果满流就证明所有的点都进，出过一次，打扫完毕，输出yes；否则no

建图总结：

• 节点含义：房间
• 边的含义：打扫路线
• 边如何相连：四连通
• 源点S：矩阵外一点
• 汇点T：矩阵外一点

代码：

#include
    
     #include
     
       #include
      
       #include
       
        #include
        
         using namespace std;#define inf 0x7fffffffint n,m,s,t,ans;int gx[5]={
    0,0,-1,0,1};int gy[5]={
    0,-1,0,1,0};//int gy[5]={0,-1,1,0,0};//int gx[5]={0,0,0,-1,1};int d[1000],id[105][105];char a[105][105];struct edge{
        int to,val,rev;    edge(int _to,int _val,int _rev)    {
            to=_to;        val=_val;        rev=_rev;    }};vector
         
          e[1000];void add(int x,int y,int w){ e[x].push_back(edge(y,w,e[y].size())); e[y].push_back(edge(x,0,e[x].size()-1));}bool bfs(){ memset(d,-1,sizeof(d)); queue
          
           q; q.push(s); d[s]=0; while(!q.empty()) { int x=q.front(); q.pop(); for(int i=0;i
           
            >a[i][j]; id[i][j]=++cnt; if(a[i][j]=='.')tot++; } } s=0; t=cnt+1; if(tot%2==1) { printf("NO\n"); continue; } if((n==1)||(m==1)) { printf("NO\n"); continue; } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(a[i][j]=='.') { if(((i+j)%2)==1) { add(s,id[i][j],2); sum+=2; for(int k=1;k<=4;k++) { int nx=i+gx[k]; int ny=j+gy[k]; if((nx>=1)&&(nx<=n)&&(ny>=1)&&(ny<=m)&&(a[nx][ny]!='#')) add(id[i][j],id[nx][ny],1); } } else { add(id[i][j],t,2); } } } } ans=0; while(bfs()) { ans+=dfs(s,inf); } if(ans==tot) { printf("YES\n"); } else printf("NO\n"); } return 0;}