댄스 체인 템 플 릿 Dancing Links
1709 단어 데이터 구조
const int maxnode = 100010;
const int MaxM = 1010;
const int MaxN = 1010;
struct DLX { //
int n, m, size; //n ,m ;
int U[maxnode], D[maxnode], L[maxnode], R[maxnode], Row[maxnode], Col[maxnode];
int H[MaxN], S[MaxM]; //S , H
int ansd, ans[MaxN]; //ansd
void init(int _n, int _m) { //
n = _n;
m = _m;
for (int i = 0; i <= m; i++) {
S[i] = 0;
U[i] = D[i] = i;
L[i] = i - 1;
R[i] = i + 1;
}
R[m] = 0; L[0] = m;
size = m;
for (int i = 1; i <= n; i++)
H[i] = -1;
}
void Link(int r, int c) { //
++S[Col[++size] = c];
Row[size] = r;
D[size] = D[c];
U[D[c]] = size;
U[size] = c;
D[c] = size;
if (H[r] < 0)H[r] = L[size] = R[size] = size;
else {
R[size] = R[H[r]];
L[R[H[r]]] = size;
L[size] = H[r];
R[H[r]] = size;
}
}
void remove(int c) { //
L[R[c]] = L[c]; R[L[c]] = R[c];
for (int i = D[c]; i != c; i = D[i])
for (int j = R[i]; j != i; j = R[j]) {
U[D[j]] = U[j];
D[U[j]] = D[j];
--S[Col[j]];
}
}
void resume(int c) { //
for (int i = U[c]; i != c; i = U[i])
for (int j = L[i]; j != i; j = L[j])
++S[Col[U[D[j]] = D[U[j]] = j]];
L[R[c]] = R[L[c]] = c;
}
bool Dance(int d) { //d
if (R[0] == 0) {
ansd = d;
return true;
}
int c = R[0];
for (int i = R[0]; i != 0; i = R[i])
if (S[i] < S[c])
c = i;
remove(c);
for (int i = D[c]; i != c; i = D[i]) {
ans[d] = Row[i];
for (int j = R[i]; j != i; j = R[j]) remove(Col[j]);
if (Dance(d + 1))return true;
for (int j = L[i]; j != i; j = L[j]) resume(Col[j]);
}
resume(c);
return false;
}
}g;
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
정수 반전Udemy 에서 공부 한 것을 중얼거린다 Chapter3【Integer Reversal】 (예) 문자열로 숫자를 반전 (toString, split, reverse, join) 인수의 수치 (n)가 0보다 위 또는 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.