题目地址：codeforces 292 B 用队列维护度数为1的点，也就是可以唯一确定的点，然后每次找v1,v2,并用v2来更新与之相连的点，，如果更新后的点度数为1，就加入队列。若最后还有为”.”的，说明无解或解不唯一。 代码如下：
;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;}
你说只有有缘人才可以取下，我看着你手中的戒指，想做你的有缘人，
