CodeCraft-20 (Div. 2)D（BFS）

 1 #define HAVE_STRUCT_TIMESPEC
 2 #include<bits/stdc++.h>
 3 #include<tuple>
 4 using namespace std;
 5 int x[1007][1007],y[1007][1007];
 6 queue<pair<int,int> >q,dq;
 7 char ans[1007][1007];
 8 typedef struct node{
 9     int x,y;
10     char to,from;
11 };
12 node tle[7];
13 int main(){
14     ios::sync_with_stdio(false);
15     cin.tie(NULL);
16     cout.tie(NULL);
17     tle[1]={0,1,'R','L'};
18     tle[2]={1,0,'D','U'};
19     tle[3]={0,-1,'L','R'};
20     tle[4]={-1,0,'U','D'};
21     int n;
22     cin>>n;
23     for(int i=1;i<=n;++i){
24         for(int j=1;j<=n;++j){
25             cin>>x[i][j]>>y[i][j];
26             if(x[i][j]==-1)
27                 q.push({i,j});
28             if(x[i][j]==i&&y[i][j]==j){
29                 ans[i][j]='X';
30                 dq.push({i,j});
31             }
32         }
33     }
34     while(!q.empty()){
35         pair<int,int>now=q.front();
36         q.pop();
37         for(int i=1;i<=4;++i){
38             int dx=now.first+tle[i].x;
39             int dy=now.second+tle[i].y;
40             if(dx>0&&dx<=n&&dy>0&&dy<=n&&x[dx][dy]==-1){//把相邻的-1全都联通，让它们在-1的联通块里无限循环
41                 ans[now.first][now.second]=tle[i].to;
42                 ans[dx][dy]=tle[i].from;
43                 break;
44             }
45         }
46     }
47     while(!dq.empty()){//以不用动的点为起点BFS
48         pair<int,int>now=dq.front();
49         dq.pop();
50         for(int i=1;i<=4;++i){
51             int dx=now.first+tle[i].x;
52             int dy=now.second+tle[i].y;
53             if(dx>0&&dx<=n&&dy>0&&dy<=n&&x[dx][dy]==x[now.first][now.second]&&y[dx][dy]==y[now.first][now.second]&&ans[dx][dy]==0){
54                 ans[dx][dy]=tle[i].from;//有相同终点的点，把它连到原本的起点
55                 dq.push({dx,dy});//加入队列，这个点已经能走到它的终点，他自己也可以成为一个中间过度点
56             }
57         }
58     }
59     for(int i=1;i<=n;++i)
60         for(int j=1;j<=n;++j)
61             if(ans[i][j]==0){
62                 cout<<"INVALID";
63                 return 0;
64             }
65     cout<<"VALID
";
66     for(int i=1;i<=n;++i){
67         for(int j=1;j<=n;++j)
68             cout<<ans[i][j];
69         cout<<"
";
70     }
71     return 0;
72 }