DLX 精確覆蓋
對于n*m的可解矩陣(我也不知道該如何描述), 行(n)存的是解空間,列(m)存的是狀態(tài)空間
hust1017 Exact Cover
此題純粹是DLX模板題.
zoj 3209 Treasure Map
n = P(圖形的個數(shù))
m = N*M(小格子的個數(shù));
spoj1771 N皇后問題
對于N*N的矩陣, 總共有N*N個位子讓你來放皇后,所以n=N*N，
而對于每個皇后能攻擊四個方向，行、列、右斜、左斜。
所以, m = N + N + (2*N-1) + (2*N-1)
for(i = 1; i <= N; ++ i) {
for(j = 1; j <= N; ++ j) {
k = (i - 1) * N + j;
link(k, i);
link(k, N+j);
link(k, 2*N+i+j-1);
link(k, 5*N+i-j-1);
}
}
如果某些皇后已經(jīng)放置, 就要刪除此皇后能攻擊到的行、列、右斜、左斜。
poj 3074， 3076 sudoku 都是數(shù)獨，一個是9*9的數(shù)獨，一個是16*16的數(shù)獨
將定要求的是一個N*N的數(shù)獨,總格有N*N個格子, 而每個格子都可以填N個數(shù)，
所有n = N*N*N
對于數(shù)獨每列、每行、每宮的數(shù)都必須不同，且還要判斷這個格子是否要被填滿
所有m = N*N + N*N + N*N + N*N;
第一個N*N表示格子是否要被填滿
第二個N*N表示要填的數(shù)在第幾行
第三個N*N表示要填的數(shù)在第幾列
第四個N*N表示要填的數(shù)在第幾宮
這四個狀態(tài)就可以確定數(shù)獨了
for(i = 0; i < N; ++ i) {
for(j = 0; j < N; ++ j) {
char ch = str[ i ][ j ];
int val = i*N+j;
int row, col;
if(ch == '-') {
for(k = 1; k <= N; ++ k) {
row = val * N + k;
col = val + 1; add(row, col);
col = N*N + i*N + k; add(row, col);
col = N*N + N*N + j*N + k; add(row, col);
col = N*N + N*N + N*N + palace(i, j) * N + k;
add(row, col);
}
}
else {
k = ch - 'A' + 1;
row = val * N + k;
col = val + 1; add(row, col);
col = N*N + i*N + k; add(row, col);
col = N*N + N*N + j*N + k; add(row, col);
col = N*N + N*N + N*N + palace(i, j) * N + k;
add(row, col);
}
}
}
hdu 3663 power station
對于一個電站只可供應它自己所在的城市和相鄰的城市且每個城市一天只能被1個電站供應。
因為求的是每個城市供應的時間段.
由于D <= 5, 所以只有16個區(qū)間段
[0,0],[1,1],[2,2],[3,3],
[4,4],[5,5],[1,2],[2,3],
[3,4],[4,5],[1,3],[2,4],
[3,5],[1,4],[2,5],[1,5]
所有n = N*16;
對于 m = N*D + N;
N*D表示第i天供應第j個城市，
由于每個電站只能運行一次，
所以N表示這是第幾個發(fā)電站供應的。
如果可以無限次發(fā)電的話 m = N*D;(應該是這個樣的吧)
hdu 2828 lamp
對于M個開關(guān), N個燈泡，選擇其中幾個開關(guān)在某種狀態(tài)下使N個燈泡都亮。
應為任意開關(guān)都有四種可能: （開關(guān)選或不選，開關(guān)ON或OFF）兩兩組合就4種
所以 n = N * 4;
開關(guān)控制的燈泡，此開關(guān)是哪個開關(guān)
所以 m = N + M;
以上原創(chuàng)且純粹給自己準備的.