CodeCraft-20 (Div. 2) D. Nash Matrix

原题链接：https://codeforces.com/contest/1316/problem/D

走到自己位置上的一定是'X'，然后同一路径上的目的地一定一样，可以从每个‘X’开始把同一目的地的都搜过去，处理出来，然后-1的情况就是反着来，所有联通的-1构成一个死循环就好了，如果最后发现有没有被处理到的，说明无法构造出来。

注意上下左右方向的判断很恶心，昨晚wa了3发才过....罚时爆炸。

代码

//#pragma GCC optimize(3)
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
typedef pair<int,int> pp;
const int N=1e3+5;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
const double pi=acos(-1);
const double eps=1e-6;
mt19937 rnd(time(0));
pp g[N][N];
int vis[N][N];
char ans[N][N];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,-1,1};
char d[4]={'U','D','R','L'};
char fd[4]={'D','U','L','R'};
void dfs(int x,int y)
{
    for(int i=0;i<4;i++){
        int xx=x+dx[i];
        int yy=y+dy[i];
        if(vis[xx][yy])continue;
        if(g[x][y].first==g[xx][yy].first&&g[x][y].second==g[xx][yy].second)
        {
            ans[xx][yy]=d[i];
            vis[xx][yy]=1;
            dfs(xx,yy);
        }
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int x,y;
            scanf("%d%d",&x,&y);
            g[i][j]={x,y};
            if(x==i&&y==j)ans[x][y]='X',vis[x][y]=1;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(g[i][j].first==-1){
                for(int k=0;k<4;k++){
                    int x=i,y=j;
                    int xx=x+dx[k];
                    int yy=y+dy[k];
                    if(g[x][y].first==g[xx][yy].first&&g[x][y].second==g[xx][yy].second)
                    {
                        ans[x][y]=fd[k];
                        vis[x][y]=1;
                        break;
                    }
                }
            }
            else {
                if(ans[i][j]=='X')dfs(i,j);
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(!vis[i][j]){
                printf("INVALID
");
                return 0;
            }
        }
    }
    printf("VALID
");
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            printf("%c",ans[i][j]);
        }puts("");
    }
    return 0;
}