DLX 精確覆蓋
對于n*m的可解矩陣(我也不知道該如何描述), 行(n)存的是解空間,列(m)存的是狀態空間
hust1017 Exact Cover
此題純粹是DLX模板題.
zoj 3209 Treasure Map
n = P(圖形的個數)
m = N*M(小格子的個數);
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);
}
}
如果某些皇后已經放置, 就要刪除此皇后能攻擊到的行、列、右斜、左斜。
poj 3074， 3076 sudoku 都是數獨，一個是9*9的數獨，一個是16*16的數獨
將定要求的是一個N*N的數獨,總格有N*N個格子, 而每個格子都可以填N個數，
所有n = N*N*N
對于數獨每列、每行、每宮的數都必須不同，且還要判斷這個格子是否要被填滿
所有m = N*N + N*N + N*N + N*N;
第一個N*N表示格子是否要被填滿
第二個N*N表示要填的數在第幾行
第三個N*N表示要填的數在第幾列
第四個N*N表示要填的數在第幾宮
這四個狀態就可以確定數獨了
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個區間段
[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表示這是第幾個發電站供應的。
如果可以無限次發電的話 m = N*D;(應該是這個樣的吧)
hdu 2828 lamp
對于M個開關, N個燈泡，選擇其中幾個開關在某種狀態下使N個燈泡都亮。
應為任意開關都有四種可能: （開關選或不選，開關ON或OFF）兩兩組合就4種
所以 n = N * 4;
開關控制的燈泡，此開關是哪個開關
所以 m = N + M;
以上原創且純粹給自己準備的.