P4929 【模板】舞蹈链（DLX）

众所周知，DLX算法是求解数独比较高效的方法

在舞蹈链算法中，有4个指针 L， R， U， D， 表示某个节点左、右、上、下的相邻节点。因为每一个链表都是循环的，所以理论上来说，无论按照 L 方向还是 R 方向都可以完整地遍历整个链表，二者没有任何区别。

但是，我奇妙地发现，L 和 R 是不能乱写的，有些时候只能按照 R 方向遍历链表，比如：

下面是一段AC代码，如果把第90行的 R 改成 L ，程序就会TLE。这完全不合情理。我在P4929这道舞蹈链模板题里随意修改 R 和 L ，却一直都是AC

万分期待大佬们来帮我解释一下！

#include <bits/stdc++.h>
using namespace std;

struct DLX
{
	static const int maxn = 1000, maxnode = 1e5;
	
	int n, sz;
	int row[maxnode], col[maxnode];
	int L[maxnode], R[maxnode], U[maxnode], D[maxnode];
	int S[maxn];
	int ans[maxn];
	
	void init(int n)
	{
		this -> n = n;
		sz = n;
		for (int x = 0; x <= n; x++)
		{
			U[x] = D[x] = x;
			L[x] = x - 1;
			R[x] = x + 1;
		}
		L[0] = n;
		R[n] = 0;
		
		memset(S, 0, sizeof(S));
	}
	
	void add_row(int r, vector<int> &columns)
	{
		if (columns.empty()) return ;
		
		int first = sz + 1;
		for (int x = 0; x < columns.size(); x++)
		{
			int c = columns[x];
			sz++;
			S[c]++;		
			L[sz] = sz - 1; R[sz] = sz + 1; D[sz] = c; U[sz] = U[c];
			D[U[c]] = sz; U[c] = sz;
			row[sz] = r; col[sz] = c;
		}
		L[first] = sz; R[sz] = first; 
	}
	
	#define FOR(i, A, s) for (int i = A[s]; i != s; i = A[i])
	
	void remove(int c)
	{
		L[R[c]] = L[c];
		R[L[c]] = R[c];
		
		FOR (x, D, c) FOR (y, R, x)
		{
			D[U[y]] = D[y];
			U[D[y]] = U[y];
			S[col[y]]--;
		}
	}
	
	void restore(int c)
	{
		FOR(x, D, c) FOR(y, L, x)
		{
			D[U[y]] = y;
			U[D[y]] = y;
			S[col[y]]++;
		}
		
		L[R[c]] = c;
		R[L[c]] = c;
	}
	
	bool dfs(int d, int &ansd, int *ans)
	{
		if (R[0] == 0)
		{
			ansd = d;
			return 1;
		}
		
		int c = R[0];
		FOR (x, R, 0) if (S[x] < S[c]) c = x;
		
		remove(c);
		FOR (x, D, c)
		{
			ans[d] = row[x];
			FOR (y, R, x) remove(col[y]);
			if (dfs(d + 1, ansd, ans)) return 1;
			FOR (y, L, x) restore(col[y]);
		}
		restore(c);
		
		return 0;
	}
};

const int SLOT = 0, ROW = 1, COL = 2, SUB = 3;

int a[10][10], ansd, ans[100];
vector<int> columns;
DLX solver;

void decode(int code, int &a, int &b, int &c)
{
	a = (code - 1) / 9 / 9;
	b = (code - 1) / 9 % 9;
	c = code % 9;
	if (c == 0) c = 9;
}

int main()
{
	solver.init(324);
	
    for (int x = 0; x < 9; x++)
    	for (int y = 0; y < 9; y++)
    		cin >> a[x][y];
    		
    for (int x = 0; x < 9; x++)
    	for (int y = 0; y < 9; y++)
    		for (int z = 1; z <= 9; z++)
    			if (a[x][y] == 0 || a[x][y] == z)
    			{
    				columns.clear();
    				columns.push_back(SLOT * 81 + x * 9 + y + 1);
    				columns.push_back(ROW * 81 + x * 9 + z);
    				columns.push_back(COL * 81 + y * 9 + z);
    				columns.push_back(SUB * 81 + (x / 3 * 3 + y / 3) * 9 + z);
    				
    				solver.add_row(x * 81 + y * 9 + z, columns);
				}
	
	
	solver.dfs(0, ansd, ans);
	
	for (int x = 0; x < ansd; x++)
	{
		int r, c, v;
		decode(ans[x], r, c, v);
		a[r][c] = v;
	}
	
	for (int x = 0; x < 9; x++)
	{
		for (int y = 0; y < 9; y++)
			cout << a[x][y] << ' ';
		cout << endl;
	}
}