第一次做构造题，做了两节晚自习 qwq
一开始我完全是正着想，首先 \(X\) 是显然的，但其他的点就不好做了，
然后我就想，可行的一般结论推不出，那就想反例，然后我想啊想......倒是想到了几个，比如说环与环之间不能有相交，环内外的点不能互相到达，跟本举不完，而且也不好实现，还是要想一般结论。
然后我就去想，怎么从 \((x, y)\) 搜到该点目标 \((tx, ty)\) , 我一开始还默认为路径的长度只能是曼哈顿距离嘞，蒙在鼓里发现这样还有点搞头
后来发现完全可以四个方向随便走，这就真的不好暴搜了。（我直接想现场砸键盘了
其实总结下来就是，一个起点不足矣得到以它的目标 \((tx,ty)\) 为终点的整张 DAG ，所以不好实现。
但是，反过来，如果从终点向四周扩展，找起点，就简单了呀？！
所以可以总结一个一般经验：做构造题，特别是构造图，一定要考虑 正难则反 。
- 考虑有限路径
正难则反，从每个终点向四周扩散，把目标都是该点的点都定上方向，这在正确构造中肯定是唯一的，所以每个点只染色一次。
- 考虑无限路径
在正确构造中，无限路径肯定成环。
此时需要一点思维，可以发现，如果找到环中的两个相邻点，要构造一个无限循环，其实只要把这两个点互相指向，同时以这两个点向外扩散找环，
这样环上所有的点最后都会跑到这两个点之间反复横跳。
当然，这样的两两点对，对于一个点，可能有四个方向四种情况的其一。
最后，构造完之后，再跑一边图，看一下有没有空的点，有空的就说明给的条件一定不能构造出一个自洽的结果。
#include <bits/stdc++.h>
#define re register int
using namespace std;
const int N = 1e3 + 10;
const int dx[4] = {0, -1, 0, 1};
const int dy[4] = {-1, 0, 1, 0};
const char rev[4] = {'R', 'D', 'L', 'U'};
struct Map
{
int tx, ty;
}g[N][N];
int n;
char ans[N][N];
void dfs(int x, int y, int sx, int sy)
{
for (re i = 0; i < 4; i ++)
{
int nx = x + dx[i], ny = y + dy[i];
Map a = g[nx][ny];
if (nx < 1 || nx > n || ny < 1 || ny > n || ans[nx][ny] || a.tx != sx || a.ty != sy)
continue;
ans[nx][ny] = rev[i];
dfs(nx, ny, sx, sy);
}
}
void work1()
{
for (re i = 1; i <= n; i ++)
for (re j = 1; j <= n; j ++)
{
Map a = g[i][j];
if (i != a.tx || j != a.ty) continue;
ans[i][j] = 'X';
dfs(i, j, a.tx, a.ty);
}
}
void work2()
{
for (re i = 1; i <= n; i ++)
for (re j = 1; j <= n; j ++)
{
if (g[i][j].tx == -1 && !ans[i][j])
{
if (g[i + 1][j].tx == -1)
ans[i][j] = 'D', ans[i + 1][j] = 'U', dfs(i, j, -1, -1), dfs(i + 1, j, - 1, -1);
else if (g[i - 1][j].tx == -1)
ans[i][j] = 'U', ans[i - 1][j] = 'D', dfs(i, j, -1, -1), dfs(i - 1, j, - 1, -1);
else if (g[i][j + 1].tx == -1)
ans[i][j] = 'R', ans[i][j + 1] = 'L', dfs(i, j, -1, -1), dfs(i, j + 1, - 1, -1);
else if (g[i][j - 1].tx == -1)
ans[i][j] = 'L', ans[i][j - 1] = 'R', dfs(i, j, -1, -1), dfs(i, j - 1, - 1, -1);
}
}
}
void print()
{
bool flag = false;
for (re i = 1; i <= n; i ++)
for (re j = 1; j <= n; j ++)
if (!ans[i][j])
{
flag = true;
break;
}
if (flag) cout << "INVALID\n";
else
{
cout << "VALID\n";
for (re i = 1; i <= n; i ++)
{
for (re j = 1; j <= n; j ++)
cout << ans[i][j];
cout << '\n';
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
for (re i = 1; i <= n; i ++)
for (re j = 1; j <= n; j ++)
cin >> g[i][j].tx >> g[i][j].ty;
work1();
work2();
print();
return 0;
}