|
一、剪枝 在搜索算法中优化中，剪枝，就是通过某种判断，避免一些不必要的遍历过程，形象的说，就是剪去了搜索树中的某些“枝条”，故称剪枝。应用剪枝优化的核心问题是设计剪枝判断方法，即确定哪些枝条应当舍弃，哪些枝条应当保留的方法。 剪枝算法按照其判断思路可大致分成两类：可行性剪枝及最优性剪枝。
POJ2676 给你一个9*9的九宫格，有部分已经填上了数字，要求将九宫格用1-9填满，每行中的数字各不相同，每列中的数字各不相同，从从第一行开始每3*3组成一个小九宫格，小九宫格中的数字也各不相同。 解题思路，从左上角开始试着填数，这个数应该是该行、该列和方块中都未出现的数字(因此，需要判断一个格子是否能填某个数)，这个方法叫做剪枝，深度优先搜索直到填满所有的数。
#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; } //从当前点(x,y)开始深度优先搜索 void dfs(int x,int y) { //flag是成功的标志，而放置数字是按行从上到下开始，因此x==9也是成功的标志 if(flag||x==9){ flag=true; return; } //(x,y)处已放置数字，放置下一个格子 while(a[x][y]){ if(y==8){ x++; y=0; } else y++; if(x==9){ flag=true; return; } } //枚举九个数字 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)根火柴构成，那么其中会有很多诸如边长为1，为2...为n的正方形，现在可以拿走一些火柴，那么就会有一些正方形被破坏掉。问，在已经拿走一些火柴的情况下，还需要拿走至少多少根就可以把所有的正方形破坏掉。 题解：可以用dancing links做，让火柴做为行，让所有的正方形作为列，且如果i火柴能让j正方形破坏掉，就让第i行第j列为1，然后做一次可重复的覆盖，取最小值便可以得到答案。另外，涉及两个优化， 1、最优化剪枝，即最好情况下也不会比当前最优值更优的剪枝。 2、不必一开始就将所有的火柴棍与正方形的对应关系加入到DLX中，应该在读完所有数据之后，判断哪些正方形已经被删除了(即该列无效)，只加入有效的结点。
#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:最大结点数 U,D,L,R：上下左右结点 C：列的头指针位置 O：储存答案 X：与O配合代表第几行（X[O[i]]]） 通过link（r,c）加点，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; }
二、坐标离散化 区域的个数：w*h的格子上画了n条或垂直或水平的宽度为1的直线，求出这些线将格子划分成了多少个区域。 已知： 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太大，不能创建w*h的数组，所以需要用到“坐标离散化” 这一技巧。如下图：
将前后左右没有变化的行列消除后并不会影响区域的个数。数组里重要存储有直线的行列以及其前后的行列就足够了。这样的话最多6n*6n就足够了，因此可以创建出数组并利用搜索求出区域的个数。 #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进行坐标离散化，并返回离散后的宽度。（对于y1,y2同理） //将x1,x2更新为离散后的x1,x2.y不变在x方向上缩小。（处理y1,y2时同理） 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); //填充新的网格 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 */ |
|
|
