Codeforces Round #292 (Div. 1) B. Drazil and Tiles(拓扑排序)

题目地址：codeforces 292 B
用队列维护度数为1的点，也就是可以唯一确定的点，然后每次找v1,v2,并用v2来更新与之相连的点，如果更新后的点度数为1，就加入队列。若最后还有为”.”的，说明无解或解不唯一。
代码如下：

#include <iostream>
#include <string.h>
#include <math.h>
#include <queue>
#include <algorithm>
#include <stdlib.h>
#include <map>
#include <set>
#include <stdio.h>
using namespace std;
#pragma comment(linker, "/STACK:102400000,102400000")
#define LL __int64
#define pi acos(-1.0)
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
const double eqs=1e-9;
int jx[]={0,0,1,-1};
int jy[]={1,-1,0,0};
int d[5002][5002], n, m;
char mp[5002][5002];
struct node
{
        int x, y;
};
queue<node>q;
bool topo()
{
        int i, j, k, x, y, a, b, h;
        node f1, f2;
        while(!q.empty()){
                f1=q.front();
                q.pop();
                if(!d[f1.x][f1.y]) continue ;
                d[f1.x][f1.y]=0;
                for(k=0;k<4;k++){
                        x=f1.x+jx[k];
                        y=f1.y+jy[k];
                        if(x>=0&&x<n&&y>=0&&y<m&&mp[x][y]==‘.‘){
                                d[x][y]--;
                                if(k==0){
                                        mp[f1.x][f1.y]=‘<‘;
                                        mp[x][y]=‘>‘;
                                }
                                else if(k==1){
                                        mp[f1.x][f1.y]=‘>‘;
                                        mp[x][y]=‘<‘;
                                }
                                else if(k==2){
                                        mp[f1.x][f1.y]=‘^‘;
                                        mp[x][y]=‘v‘;
                                }
                                else{
                                        mp[f1.x][f1.y]=‘v‘;
                                        mp[x][y]=‘^‘;
                                }
                                for(h=0;h<4;h++){
                                        a=x+jx[h];
                                        b=y+jy[h];
                                        if(a>=0&&a<n&&b>=0&&b<m&&mp[a][b]==‘.‘){
                                                d[a][b]--;
                                                if(d[a][b]==1){
                                                        f2.x=a;f2.y=b;
                                                        q.push(f2);
                                                }
                                        }
                                }
                        }
                }
        }
        for(i=0;i<n;i++){
                for(j=0;j<m;j++){
                        if(mp[i][j]==‘.‘) return 0;
                }
        }
        return 1;
}
int main()
{
        int i, j, x, y, cnt, k, ans;
        while(scanf("%d%d",&n,&m)!=EOF){
                for(i=0;i<n;i++){
                        scanf("%s",mp[i]);
                }
                node f;
                for(i=0;i<n;i++){
                        for(j=0;j<m;j++){
                                if(mp[i][j]!=‘.‘) continue ;
                                cnt=0;
                                for(k=0;k<4;k++){
                                        x=i+jx[k];
                                        y=j+jy[k];
                                        if(x>=0&&x<n&&y>=0&&y<m&&mp[x][y]==‘.‘) cnt++;
                                }
                                d[i][j]=cnt;
                                if(cnt==1){
                                        f.x=i;f.y=j;
                                        q.push(f);
                                }
                        }
                }
                if(topo()){
                        for(i=0;i<n;i++){
                                printf("%s\n",mp[i]);
                        }
                }
                else puts("Not unique");
        }
        return 0;
}