【題解】Codeforces 1316D. Nash Matrix

#include <iostream>
#include <queue>
using namespace std;
#define F first
#define S second
 
int n, x[1005][1005], y[1005][1005], dx[4] = {0, 0, 1, -1}, dy[4] = {1, -1, 0, 0};
char ans[1005][1005], dc[4] = {'R', 'L', 'D', 'U'};
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    queue <pair<int, int> > q;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            cin >> x[i][j] >> y[i][j];
            if (x[i][j] == i && y[i][j] == j){
                q.push({i, j});
                ans[i][j] = 'X';
            }
        }
    }
    pair<int, int> p;
    while (!q.empty()){
        p = q.front();
        q.pop();
        if (p.F != 1){
            if (x[p.F-1][p.S] == x[p.F][p.S] && y[p.F-1][p.S] == y[p.F][p.S]){
                if (!ans[p.F-1][p.S]){
                    ans[p.F-1][p.S] = 'D';
                    q.push({p.F-1, p.S});
                }
            }
        }
        if (p.F != n){
            if (x[p.F+1][p.S] == x[p.F][p.S] && y[p.F+1][p.S] == y[p.F][p.S]){
                if (!ans[p.F+1][p.S]){
                    ans[p.F+1][p.S] = 'U';
                    q.push({p.F+1, p.S});
                }
            }
        }
        if (p.S != 1){
            if (x[p.F][p.S-1] == x[p.F][p.S] && y[p.F][p.S-1] == y[p.F][p.S]){
                if (!ans[p.F][p.S-1]){
                    ans[p.F][p.S-1] = 'R';
                    q.push({p.F, p.S-1});
                }
            }
        }
        if (p.S != n){
            if (x[p.F][p.S+1] == x[p.F][p.S] && y[p.F][p.S+1] == y[p.F][p.S]){
                if (!ans[p.F][p.S+1]){
                    ans[p.F][p.S+1] = 'L';
                    q.push({p.F, p.S+1});
                }
            }
        }
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            if (x[i][j] == -1){
                for (int k = 0; k < 4; k++){
                    if (x[i+dx[k]][j+dy[k]] == -1){
                        ans[i][j] = dc[k];
                        break;
                    }
                }
            }
        }
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            if (ans[i][j] == 0){
                cout << "INVALID\n";
                return 0;
            }
        }
    }
    cout << "VALID\n";
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= n; j++){
            cout << ans[i][j];
        }
        cout << "\n";
    }
}