DLX 精確覆蓋
對(duì)于n*m的可解矩陣(我也不知道該如何描述), 行(n)存的是解空間,列(m)存的是狀態(tài)空間
hust1017 Exact Cover
此題純粹是DLX模板題.
zoj 3209 Treasure Map
n = P(圖形的個(gè)數(shù))
m = N*M(小格子的個(gè)數(shù));
spoj1771 N皇后問(wèn)題
對(duì)于N*N的矩陣, 總共有N*N個(gè)位子讓你來(lái)放皇后,所以n=N*N，
而對(duì)于每個(gè)皇后能攻擊四個(gè)方向，行、列、右斜、左斜。
所以, 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)放置, 就要?jiǎng)h除此皇后能攻擊到的行、列、右斜、左斜。
poj 3074， 3076 sudoku 都是數(shù)獨(dú)，一個(gè)是9*9的數(shù)獨(dú)，一個(gè)是16*16的數(shù)獨(dú)
將定要求的是一個(gè)N*N的數(shù)獨(dú),總格有N*N個(gè)格子, 而每個(gè)格子都可以填N個(gè)數(shù)，
所有n = N*N*N
對(duì)于數(shù)獨(dú)每列、每行、每宮的數(shù)都必須不同，且還要判斷這個(gè)格子是否要被填滿
所有m = N*N + N*N + N*N + N*N;
第一個(gè)N*N表示格子是否要被填滿
第二個(gè)N*N表示要填的數(shù)在第幾行
第三個(gè)N*N表示要填的數(shù)在第幾列
第四個(gè)N*N表示要填的數(shù)在第幾宮
這四個(gè)狀態(tài)就可以確定數(shù)獨(dú)了
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
對(duì)于一個(gè)電站只可供應(yīng)它自己所在的城市和相鄰的城市且每個(gè)城市一天只能被1個(gè)電站供應(yīng)。
因?yàn)榍蟮氖敲總€(gè)城市供應(yīng)的時(shí)間段.
由于D <= 5, 所以只有16個(gè)區(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;
對(duì)于 m = N*D + N;
N*D表示第i天供應(yīng)第j個(gè)城市，
由于每個(gè)電站只能運(yùn)行一次，
所以N表示這是第幾個(gè)發(fā)電站供應(yīng)的。
如果可以無(wú)限次發(fā)電的話 m = N*D;(應(yīng)該是這個(gè)樣的吧)
hdu 2828 lamp
對(duì)于M個(gè)開(kāi)關(guān), N個(gè)燈泡，選擇其中幾個(gè)開(kāi)關(guān)在某種狀態(tài)下使N個(gè)燈泡都亮。
應(yīng)為任意開(kāi)關(guān)都有四種可能: （開(kāi)關(guān)選或不選，開(kāi)關(guān)ON或OFF）兩兩組合就4種
所以 n = N * 4;
開(kāi)關(guān)控制的燈泡，此開(kāi)關(guān)是哪個(gè)開(kāi)關(guān)
所以 m = N + M;
以上原創(chuàng)且純粹給自己準(zhǔn)備的.