算法-搜索

谢勇湘潭大学信息工程学院[e-mail]3.搜索PKU2386W表示水，可以连接8个方向，问有几块独立的水域1012W........WW..算法框架dfs_visit(状态u){u标记为已访问;foreachu的可达且未访问过的状态v{dfs_visit(v);}}dfs(状态集合s[]){foreachs[i]{if(s[i]未访问)dfs_visit(s[i]);}}charmap[111][111];intdir[8][2]={{0,1},{0,-1},{1,0},{-1,0},{1,1},{1,-1},{-1,1},{-1,-1}};voiddfs(intx,inty){inti;map[x][y]='.';for(i=0;i8;i++)if(map[x+dir[i][0]][y+dir[i][1]]=='W')dfs(x+dir[i][0],y+dir[i][1]);}intmain(){intn,m,i,j,cnt=0;scanf(%d%d,&n,&m);getchar();memset(map,'.',sizeof((n+1)*(m+1)));for(i=1;i=n;i++){for(j=1;j=m;j++)map[i][j]=getchar();getchar();}for(i=1;i=n;i++){for(j=1;j=m;j++)if(map[i][j]=='W')cnt++,dfs(i,j);}printf(%d\n,cnt);return0;}PKU1190题目大意制作一个体积为Nπ的M层生日蛋糕，每层都是一个圆柱体。设从下往上数第i(1=i=M)层蛋糕是半径为Ri,高度为Hi的圆柱。当iM时，要求RiRi+1且HiHi+1。希望蛋糕外表面（最下一层的下底面除外）的面积Q最小。表面积只和底层圆面积和各层侧面积相关Q=Sπ2112miiiSRRH21miiiNRH状态(i,Ri,Hi,Si-1,Di-1)转移后的状态(i+1,Ri+1,Hi+1,Si-1+2RiHi,Di-1+Ri2Hi)枚举所有的Ri+1,Hi+1,保证Ri+1RiHi+1Himin_d[i]表示做上面i层最小体积min_s[i]表示做上面i层最小侧面积显然易见的剪枝Si-1+2RiHi+min_s[m-i]=bestDi-1+Ri2Hi+min_d[m-i]N从k层到m层增加的侧面积所以当s+2*剩余体积/Rk=best时可以剪枝2222*miimikiikikkRHRHRR剩余体积#defineINF0x3f3f3f3fintmin=INF;intn,m;intmins[21],mind[21];voidinit(){inti;mins[0]=0;mind[0]=0;for(i=1;i=20;i++){mins[i]=mins[i-1]+2*i*i;mind[i]=mind[i-1]+i*i*i;}}voiddfs(intk,intr,inth,ints,intd){inti,j,ld;if(k==m){if(d==n&&smin)min=s;return;}ld=n-d;for(i=r-1;im-k-1;i--){intmaxh,ts=0,td;maxh=(ld-mind[m-k-1])/(i*i);if(maxhh-1)maxh=h-1;for(j=maxh;jm-k-1;j--){td=ld-i*i*j;if(tdmind[m-k-1])continue;if(k==0)ts=i*i+2*i*j;elsets=s+2*i*j;if(ts+mins[m-k-1]=min||ts+2*td/i=min)continue;dfs(k+1,i,j,ts,d+i*i*j);}}}PKU3126题意给定两个四位素数a，b，要求把a变换到b变换的过程要保证每次变换出来的数都是一个四位素数，而且当前这步的变换所得的素数与前一步得到的素数只能有一个位不同，而且每步得到的素数都不能重复。求从a到b最少需要的变换次数。无法变换则输出Impossible队列Q;Q.enque(起始状态,0)；起始状态已达；while(Q非空){t=Q.front();Q.deque();if(t.state为结束状态）返回t.step;对于t的任何可达且未达到状态u{Q.enque(u,t.step+1);u已达;}}返回不可达；队列顺序表先入先出C++queue模板C直接用数组+头尾下标变量实现▪数组容量=所有入队的状态数cinse;queuePIIq;q.push(MP(s,0));memset(vis,0,sizeof(vis));vis[s]=1;while(!q.empty()){PIIa=q.front();q.pop();if(a.first==e){couta.secondendl;gotonext;}intk=a.first%1000;for(i=1000;i10000;i+=1000)if(!t[i+k]&&!vis[i+k])q.push(MP(i+k,a.second+1)),vis[i+k]=1;k=a.first%100+a.first/1000*1000;for(i=0;i1000;i+=100)if(!t[i+k]&&!vis[i+k])q.push(MP(i+k,a.second+1)),vis[i+k]=1;k=a.first%10+a.first/100*100;for(i=0;i100;i+=10)if(!t[i+k]&&!vis[i+k])q.push(MP(i+k,a.second+1)),vis[i+k]=1;k=a.first/10*10;for(i=1;i10;i+=2)if(!t[i+k]&&!vis[i+k])q.push(MP(i+k,a.second+1)),vis[i+k]=1;}coutImpossibleendl;next:;PKU10778数码问题输出一组移动的方向路径123x4675812345678xBFS将x认为9（也可以认为0，9更方便些）状态可以用一个数字串表示123456789为终止状态状态数为9！由于需要打印路径，所以需要记录下某个节点的前驱节点以及转换方向所以队列在出队时，不用删除队头直接用数组实现队列如果使用C++的queue，需要另外开辟数组来存节点的前驱。structnode{charstr[9];//数码串chardir;//转换方向inthf;//序号intpos;//9的位置intpre;//上个节点的位置}queue[QS];123946758123496758123469758193426758123456798intcv[9][4]={-1,1,-1,3,0,2,-1,4,1,-1,-1,5,-1,4,0,6,3,5,1,7,4,-1,2,8,-1,7,3,-1,6,8,4,-1,7,-1,5,-1};Cantor展开算排列在全排列中的序号123456789=0123456798=1序号=SUM(Ci*(8-i)!)，i=0,1,...,7intfac[8]={1,2,6,24,120,720,5040,40320};inthash(char*a){inti,j,s=0,c;for(i=0;i8;i++){for(c=0,j=i+1;j9;j++)if(a[i]a[j])c++;s+=c*fac[7-i];}returns;}intmain(){chart,b[9];inti,pos,hf;structnode*p,*q;p=queue+tail;for(i=0;i9;i++){while((t=getchar())=='');if(t=='x')p-str[i]=9,p-pos=i;elsep-str[i]=t-'0';}p-pre=-1;p-hf=hash(p-str);vis[p-hf]=1;tail++;while(head!=tail){p=queue+head;head++;if(p-hf==0){prt_path(head-1);putchar('\n');return0;}pos=p-pos;for(i=0;i4;i++){if(cv[pos][i]!=-1){memcpy(b,p-str,9);t=b[pos];b[pos]=b[cv[pos][i]];b[cv[pos][i]]=t;hf=hash(b);if(!vis[hf]){q=queue+tail++;memcpy(q-str,b,9);q-pos=cv[pos][i];q-pre=head-1;q-dir=dir[i];q-hf=hf;vis[hf]=1;}}}}puts(unsolvable);return0;}不是所有的时候都有类似cantor展开这样计算出唯一序号的判重方法更加常用的是hashhash函数进行定位▪Hash(x)=x%HASH_SIZE;链地址法解决冲突▪可能存在x1，x2,x1!=x2,但Hash(x1)=Hash(x2)▪同一Hash地址上存放一个链表。intpre[HS];//初始化为-1;inthk[HS][2];inthcnt=0;inthash(char*a){inti,s=0;for(i=0;i9;i++)s=s*10+a[i];returns;}intinsert(ints){inthash=s%HS;intu=pre[hash];while(u!=-1){if(hk[u][0]==s)return0;u=hk[u][1];}hk[hcnt][0]=s;hk[hcnt][1]=pre[hash];pre[hash]=hcnt++;return1;}intmain(){chart,b[9];inti,pos,hf,s;structnode*p,*q;memset(pre,-1,sizeof(pre));p=queue+tail;for(i=0;i9;i++){while((t=getchar())=='');if(t=='x')p-str[i]=9,p-pos=i;elsep-str[i]=t-'0';}p-pre=-1;p-hf=hash(p-str);insert(p-hf);tail++;while(head!=tail){p=queue+head;head++;if(p-hf==123456789){prt_path(head-1);putchar('\n');return0;}pos=p-pos;for(i=0;i4;i++){if(cv[pos][i]!=-1){memcpy(b,p-str,9);t=b[pos];b[pos]=b[cv[pos][i]];b[cv[pos][i]]=t;hf=hash(b);if(insert(hf)){q=queue+tail++;memcpy(q-str,b,9);q-pos=cv[pos][i];q-pre=head-1;q-dir=dir[i];q-hf