\(\\\)

---

给出一个\(N\times M\) 的网格，一些位置是障碍，其他位置是空地，求是否存在一个用 \(1\times 2\)的骨牌铺满空地的方案，以及方案是否唯一。

骨牌不能放到网格以外，不能重叠，不能覆盖在障碍物上。

• \(N,M\le 2000\)

\(\\\)

\(Solution\)

---

巧妙的思路题。

注意到有一些位置的方案是唯一的。如果一个空格的周围四联通部分只有一个空格，那么必定有一个骨牌要放在这两个格子上。同时，这一次放置可能会影响另一个格子的四联通部分的选择方案。

这就像一个拓扑排序。首先记录每一个点四联通的格子里空地的数量，将数量为\(1\)的放进队列里，然后逐个放置，\(check\) 周围是否有新出现的方案唯一的格子。

最后如果所有空地被填满了，方案就唯一，反之多解。

出题人比较良心，无解和多解都输出 "Not unique" ，所以不需要再判断无解。

\(\\\)

\(Code\)

---

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define R register#define gc getchar#define N 2010using namespace std;inline int rd(){ int x=0; bool f=0; char c=gc(); while(!isdigit(c)){if(c=='-')f=1;c=gc();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();} return f?-x:x;}char mp[N][N];int n,m,cnt,num[N][N],deg[N][N];int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};queue
            
             
               > q;inline void inq(int x,int y){ for(R int i=0;i<4;++i){ --deg[x+dx[i]][y+dy[i]]; if(deg[x+dx[i]][y+dy[i]]==1) q.push(make_pair(x+dx[i],y+dy[i])); }}int main(){ n=rd(); m=rd(); char c=gc(); for(R int i=1;i<=n;++i) for(R int j=1;j<=m;++j){ while(c!='.'&&c!='*') c=gc(); mp[i][j]=c; c=gc(); } for(R int i=1;i<=n;++i) for(R int j=1;j<=m;++j) if(mp[i][j]=='.'){ deg[i][j]=(mp[i-1][j]=='.')+(mp[i+1][j]=='.')+(mp[i][j-1]=='.')+(mp[i][j+1]=='.'); if(deg[i][j]==1) q.push(make_pair(i,j)); } while(!q.empty()){ int x=q.front().first; int y=q.front().second; q.pop(); if(deg[x][y]!=1) continue; if(mp[x+1][y]=='.'){ mp[x][y]='^'; mp[x+1][y]='v'; inq(x+1,y); } if(mp[x-1][y]=='.'){ mp[x-1][y]='^'; mp[x][y]='v'; inq(x-1,y); } if(mp[x][y+1]=='.'){ mp[x][y]='<'; mp[x][y+1]='>'; inq(x,y+1); } if(mp[x][y-1]=='.'){ mp[x][y-1]='<'; mp[x][y]='>'; inq(x,y-1); } } for(R int i=1;i<=n;++i) for(R int j=1;j<=m;++j) if(mp[i][j]=='.'){puts("Not unique");return 0;} for(R int i=1;i<=n;++i){ for(R int j=1;j<=m;++j) putchar(mp[i][j]); puts(""); } return 0;}