UVA11882 Biggest Number强剪枝
分类：——-acm——└──搜索
c++
题目链接：
UVA11882
解题思路:
常规思路是 枚举每个点,暴力dfs,然后选择最大的那个 但题目只给了1000MS 这就需要剪枝了
剪枝1:
假设当前答案长度为ans，那么当我们走到一个点(x, y)的时候，bfs一下判断能接触的格子数。假设现在能从(x, y)走到的点，我们都能到达，这是最好的情况。设从(x, y)能走到的点数为maxlen，，那么如果从出发点走到(x, y)经过的格子，加上maxlen，都没有ans的长度大，那么不管从(x, y)怎么搜，我们都不能取代我们现在的ans（长才是王道懂不懂），那么直接回溯，不要这个点了。这个剪枝效力还是不错的。
而如果等于的话 我们需要一个标记 flag 来表示当前串和 ans串的大小关系
剪枝2: 如果ans串已经是最大可能长度 且搜索的起点小于ans串的起点 则直接跳过
代码：
#include<iostream>#include<cstdio>#include<cstring>#include<queue>#include<time.h>#define printime printf("%.3lf\n",(double)clock() / CLOCKS_PER_SEC)#define maxn 33using namespace std;struct node{int x,y;}que[10050],u;char ans[maxn],temp[maxn];int dir[4][2]={1,0,-1,0,0,1,0,-1};char map[maxn][maxn];char g[maxn][maxn];int sum;int max_len;int n,m;int ok(int x,int y){if(x<1||y<1||x>n||y>m)return 0;return 1;}int bfs(int x,int y){for(int i=1;i<=n;i++)strcpy(g[i]+1,map[i]+1);int head=0,tail=0;int tx,ty;que[tail++]=(node){x,y};while(head<tail){u=que[head++];for(int i=0;i<4;i++){tx=u.x+dir[i][0];ty=u.y+dir[i][1];if(!ok(tx,ty)||g[tx][ty]=='#')continue;g[tx][ty]='#';que[tail++]=(node){tx,ty};}}return head;}int flag;void dfs(int x,int y,int len){if(len>max_len||(len==max_len&&flag==1)){max_len=len;temp[len]='\0';strcpy(ans,temp);flag=0;//一个起点得到新的ans串 需要继续比较}// printf("x=%d y=%d len=%d flag=%d\n",x,y,len,flag);int res=bfs(x,y);if(len+res-1<max_len||(len+res-1==max_len&&flag==-1)) //剪枝1return;int tx,ty;for(int i=0;i<4;i++){tx=x+dir[i][0];ty=y+dir[i][1];if(!ok(tx,ty)||map[tx][ty]=='#')continue;temp[len]=map[tx][ty];map[tx][ty]='#';if(flag==0){if(temp[len]<ans[len])flag=-1;else if(temp[len]>ans[len])flag=1;dfs(tx,ty,len+1);flag=0;//回溯}elsedfs(tx,ty,len+1);map[tx][ty]=temp[len];}}int main(){// freopen("in.txt","r",stdin);while(scanf("%d%d",&n,&m)&&(m+n)){sum=0;max_len=0;memset(ans,'\0',sizeof(ans));memset(temp,'\0',sizeof(temp));for(int i=1;i<=n;i++){scanf("%s",map[i]+1);for(int j=1;j<=m;j++)if(map[i][j]!='#')sum++;}for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(map[i][j]!='#'){if(max_len==sum&&map[i][j]<ans[0]) //剪枝2continue;temp[0]=map[i][j];map[i][j]='#';if(ans[0]==temp[0])flag=0;else if(temp[0]>ans[0])flag=1;elseflag=-1;dfs(i,j,1);map[i][j]=temp[0];}}printf("%s\n",ans);//printime;}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
上一篇poj3322 Bloxorz I状压BFS下一篇zoj2587 Unique Attack判断最小割是否唯一
顶0踩0
只要你扬帆，便会有八面来风。启程了，人的生命才真正开始。
