一、剪枝
在搜索算法中優(yōu)化中，剪枝，就是通過(guò)某種判斷，避免一些不必要的遍歷過(guò)程，形象的說(shuō)，就是剪去了搜索樹(shù)中的某些“枝條”，故稱(chēng)剪枝。應用剪枝優(yōu)化的核心問(wèn)題是設計剪枝判斷方法，即確定哪些枝條應當舍棄，哪些枝條應當保留的方法。
剪枝算法按照其判斷思路可大致分成兩類(lèi)：可行性剪枝及最優(yōu)性剪枝。
POJ2676
給你一個(gè)9*9的九宮格，有部分已經(jīng)填上了數字，要求將九宮格用1-9填滿(mǎn)，每行中的數字各不相同，每列中的數字各不相同，從從第一行開(kāi)始每3*3組成一個(gè)小九宮格，小九宮格中的數字也各不相同。
解題思路，從左上角開(kāi)始試著(zhù)填數，這個(gè)數應該是該行、該列和方塊中都未出現的數字(因此，需要判斷一個(gè)格子是否能填某個(gè)數)，這個(gè)方法叫做剪枝，深度優(yōu)先搜索直到填滿(mǎn)所有的數。
#include
#include
using name space std;
int a[10][10];
char s[10][10];
//下標都是從0到8
//判斷(x,y)處能否放置k
bool flag;
bool ok(int k,int x,int y)
{
for(int i=0;i<>
if(a[i][y]==k) return false;
}
for(int j=0;j<>
if(a[x][j]==k) return false;
}
int u=x-x%3,v=y-y%3;
for(int i=u;i<>
for(int j=v;j<>
if(a[i][j]==k) return false;
}
}
return true;
}
//從當前點(diǎn)(x,y)開(kāi)始深度優(yōu)先搜索
void dfs(int x,int y)
{
//flag是成功的標志，而放置數字是按行從上到下開(kāi)始，因此x==9也是成功的標志
if(flag||x==9){
flag=true;
return;
}
//(x,y)處已放置數字，放置下一個(gè)格子
while(a[x][y]){
if(y==8){
x++;
y=0;
}
else y++;
if(x==9){
flag=true;
return;
}
}
//枚舉九個(gè)數字
for(int k=1;k<>
if(ok(k,x,y)){
a[x][y]=k;
if(y==8) dfs(x+1,0);
else dfs(x,y+1);
if(flag) return;
a[x][y]=0;
}
}
}
int main()
{
int t;
scanf('%d',&t);
while(t--){
for(int i=0;i<>
scanf('%s',s[i]);
for(int j=0;j<>
a[i][j]=s[i][j]-'0';
}
}
flag=false;
dfs(0,0);
for(int i=0;i<>
for(int j=0;j<>
printf('%d',a[i][j]);
}
printf('\n');
}
}
return 0;
}
POJ1084
題意：n*n的矩形陣(n<>，由2*n*(n+1)根火柴構成，那么其中會(huì )有很多諸如邊長(cháng)為1，為2...為n的正方形，現在可以拿走一些火柴，那么就會(huì )有一些正方形被破壞掉。問(wèn)，在已經(jīng)拿走一些火柴的情況下，還需要拿走至少多少根就可以把所有的正方形破壞掉。
題解：可以用dancing links做，讓火柴做為行，讓所有的正方形作為列，且如果i火柴能讓j正方形破壞掉，就讓第i行第j列為1，然后做一次可重復的覆蓋，取最小值便可以得到答案。另外，涉及兩個(gè)優(yōu)化，
1、最優(yōu)化剪枝，即最好情況下也不會(huì )比當前最優(yōu)值更優(yōu)的剪枝。
2、不必一開(kāi)始就將所有的火柴棍與正方形的對應關(guān)系加入到DLX中，應該在讀完所有數據之后，判斷哪些正方形已經(jīng)被刪除了(即該列無(wú)效)，只加入有效的結點(diǎn)。
#include
#include
#include
using name space std;
const int inf=1<>
const int NUM=100*60;
int cnt,L[NUM],R[NUM],S[NUM],D[NUM],U[NUM],C[NUM],O[NUM],H[NUM],X[NUM];
/*
NUM:最大結點(diǎn)數
U,D,L,R：上下左右結點(diǎn)
C：列的頭指針位置
O：儲存答案
X：與O配合代表第幾行（X[O[i]]]）
通過(guò)link（r,c）加點(diǎn)，dfs（0）運算
*/
void remove(int c)
{
for(int i=D[c];i!=c;i=D[i])
{
L[R[i]]=L[i];
R[L[i]]=R[i];
}
}
void resume(int c)
{
for(int i=D[c];i!=c;i=D[i])
{
L[R[i]]=i;
R[L[i]]=i;
}
}
int geth()
{
bool has[80];
memset(has, false, sizeof(has));
int res=0;
for(int i=R[0]; i!=0; i=R[i])
if(!has[i])
{
res++;
for(int j=D[i]; j!=i; j=D[j])
for(int k=R[j]; k!=j; k=R[k])
has[C[k]]=true;
}
return res;
}
int ans;
void dfs(int k)
{
if(!R[0])
{
ans=min(k,ans);
return;
}
else if(k+geth()>=ans)
return;
int c=R[0];
for(int t=R[0],ms=inf; t!=0; t=R[t])
if(S[t]<>
ms=S[t],c=t;
for(int i=D[c];i!=c;i=D[i])
{
remove(i);
for(int j=R[i]; j!=i; j=R[j])
{
remove(j);
S[C[j]]--;
}
dfs(k+1);
for(int j=L[i]; j!=i; j=L[j])
{
resume(j);
S[C[j]]++;
}
resume(i);
}
}
void build(int r,int c)
{
for(int i=0;i<>
{
U[i]=D[i]=i;
L[i+1]=i;
R[i]=i+1;
C[i]=i;
S[i]=0;
}
R[cnt=c]=0;
while(r)
H[r--]=-1;
}
void link(int r,int c)
{
++S[C[++cnt]=c];
X[cnt]=r;
D[cnt]=D[c];
U[D[c]]=cnt;
U[cnt]=c;
D[c]=cnt;
if(H[r]<>
H[r]=L[cnt]=R[cnt]=cnt;
else
{
R[cnt]=R[H[r]];
L[R[H[r]]]=cnt;
L[cnt]=H[r];
R[H[r]]=cnt;
}
}
bool mark[80][80];
void init(int n)
{
memset(mark,false,sizeof(mark));
int i,j,k,si,num=0,c=1;
for(si=1;si<>
{
for(i=1;i<>
{
for(j=1;j<>
{
for(k=0;k<>
{
mark[(i-1)*(2*n+1)+j+k][c]=true;
mark[(i-1+si)*(2*n+1)+j+k][c]=true;
mark[i*n+(i-1)*(n+1)+j+k*(2*n+1)][c]=true;
mark[i*n+(i-1)*(n+1)+j+k*(2*n+1)+si][c]=true;
}
c++;
}
}
}
}
int main()
{
int T,n;
for(scanf('%d',&T);T;T--)
{
scanf('%d',&n);
int num,row=2*n*(n+1),col=0;
for(int i=1;i<>
col+=i*i;
build(row,col);
init(n);
scanf('%d',&num);
bool vis[80];
memset(vis,false,sizeof(vis));
for(int i=0;i<>
{
int r;
scanf('%d',&r);
for(int j=1;j<>
{
if(mark[r][j])
{
if(!vis[j])
{
vis[j]=true;
R[L[j]]=R[j];
L[R[j]]=L[j];
R[j]=L[j]=0;
}
}
}
}
for(int i=1;i<>
for(int j=1;j<>
if(mark[i][j]&&!vis[j])
link(i,j);
ans=100000;
dfs(0);
printf('%d\n',ans);
}
return 0;
}
二、坐標離散化
區域的個(gè)數：w*h的格子上畫(huà)了n條或垂直或水平的寬度為1的直線(xiàn)，求出這些線(xiàn)將格子劃分成了多少個(gè)區域。
已知：
1≤w,h≤1000000
1≤n≤500
sample input
w= 10,h = 10,n = 5
x1= {1 , 1 , 4 , 9 , 10}
y1= {4 , 8 , 1 , 1 , 6}
x2= {6 , 10 , 4 , 9 , 10}
y2= {4 , 8 , 10 , 5 , 10}
(對應上圖，橫向為x，縱向為y)
利用BFS或dfs可以求出被分割的區域，但是w,h太大，不能創(chuàng )建w*h的數組，所以需要用到“坐標離散化” 這一技巧。如下圖：
將前后左右沒(méi)有變化的行列消除后并不會(huì )影響區域的個(gè)數。數組里重要存儲有直線(xiàn)的行列以及其前后的行列就足夠了。這樣的話(huà)最多6n*6n就足夠了，因此可以創(chuàng )建出數組并利用搜索求出區域的個(gè)數。
#include
#include
#include
#include
#include
#include
#include
using name space std;
const int maxn = 500;
int W,H,N;
int X1[maxn],X2[maxn],Y1[maxn],Y2[maxn];
bool fld[maxn*6][maxn*6];
int dx[4]={0,0,-1,1};
int dy[4]={1,-1,0,0};
//對x1和x2進(jìn)行坐標離散化，并返回離散后的寬度。（對于y1,y2同理）
//將x1,x2更新為離散后的x1,x2.y不變在x方向上縮小。（處理y1,y2時(shí)同理）
int compress(int *x1,int *x2,int w)
{
vector
for(int i = 0;i <>//確定離散后x軸上哪些值還存在
{
for(int d = -1;d <= 1;="">
{
int tx1 = x1[i] + d, tx2 = x2[i] +d;
if(1 <= tx1="" &&="" tx1=""><=w)>
if(1 <= tx2="" &&="" tx2=""><=w)>
}
}
sort(xs.begin(),xs.end());
xs.erase(unique(xs.begin(),xs.end()),xs.end());//去重
for(int i = 0; i < n;="">//轉化為新的x1,x2;
{
x1[i] =find(xs.begin(),xs.end(),x1[i])-xs.begin();
x2[i] =find(xs.begin(),xs.end(),x2[i])-xs.begin();
}
return xs.size();
}
void solve()
{
//離散化
W = compress(X1,X2,W);
H = compress(Y1,Y2,H);
//填充新的網(wǎng)格
memset(fld,0,sizeof(fld));
for(int i=0;i<>
{
for(int y=Y1[i];y<>
{
for(int x=X1[i];x<>
{
fld[y][x]=true;
}
}
}
//利用BFS計算區域數
int ans=0;
for(int y=0;y<>
{
for(int x=0;x<>
{
if(fld[y][x]) continue;
ans++;
queue<>
que.push(make_pair(x,y));
while(!que.empty())
{
int sx=que.front().first,sy=que.front().second;
que.pop();
for(int i=0;i<>
{
int tx=sx + dx[i],ty=sy +dy[i];
if(tx<0 ||="" tx="">=W ||ty<0 ||="" ty="">=H || fld[ty][tx]) continue;
que.push(make_pair(tx,ty));
fld[ty][tx]=true;
}
}
}
}
printf('%d\n',ans);
}
intmain()
{
while(scanf('%d%d%d',&W,&H,&N)==3)
{
for(int i=0;i<>
scanf('%d',&X1[i]);
for(int i=0;i<>
scanf('%d',&X2[i]);
for(int i=0;i<>
scanf('%d',&Y1[i]);
for(int i=0;i<>
scanf('%d',&Y2[i]);
solve();
}
return 0;
}
/*
輸入：
1010 5
11 4 9 10
610 4 9 10
48 1 1 6
48 10 5 10
輸出：
6
*/
聯(lián)系客服
