1286: [蓝桥杯2016初赛]剪邮票 搜索与联通分量

题目

题目链接

所遇问题

深搜

当时想到可以用dfs，但是发现答案不对，后来输出答案发现对于

这种情况没有
后来才想起对于深搜他会一直搜到底，

所以假如他搜索一开始走1这条路，走到底发现不够5个数，就会放弃这条路，然后递归一步一步退回去，再走2这条路，发现2这条路只有三个数可以选，所以说也放弃。但其实我们想要的答案是这两个路加起来。但是单纯的dfs不能实现。
当时这种思路难点在如何避免重复搜！！！

组合树

其实这个题相当于我从12个格子里选择五个格子，要去是这几个格子要连起来。也就相当于从0到11中选择5个数。
然后写了递归，但是对于1 2 3 4 5与5 4 3 2 1情况，按理说是一种情况，所以要组合不要排列。然后写了代码（错误的）

for(int i=p;i<=12;i++){
      //这样搜肯定有问题啊，因为12345 与54321会认为两个排列，那样的话求出来的是一样的啊 ,所以让//i从p开始，也就是说每次都将是升序排列的 if(mark[i]==0){
    mark[i]=1;a[step]=i;dfs(step+1,p+1);mark[i]=0;//a[step]=0;}}

然后还是有重复的
错误一：如果你在找一个数，但是i已经从第11个数开始循环找了，肯定找不够5个数了。
所以

for(int i=p;i<=12-(5-step);i++){
     //这个12-（5-step）(step表示搜索深度)

另一个，传参时，

	dfs(step+1,p+1);

正确的是

	dfs(step+1,i+1);

	for(int i=p;i<=12-(5-step);i++){
      a[step]=i;dfs(step+1,i+1);//这个地方，应该传i，这样组合出来的数是递增的}}

dfs判断连通度

就是搜多次，把能走到的地方都标记

void dfs_2(int x,int y){
    for(int i=0;i<4;i++){
    int dx=x+to[i][0];int dy=y+to[i][1];if(dx<0||dx>2||dy<0||dy>3||book_2[dx][dy]||book[dx][dy]==0){
    continue;}book_2[dx][dy]=true;dfs_2(dx,dy);}
}

ac代码

#include<bits/stdc++.h>
#include<cstring>
using namespace std;
int book[6][6];
int ans;
int a[5];
int mark[14];
int to[4][2]={
    {
    0,1},{
    1,0},{
    0,-1},{
    -1,0}};//右，下，左,不允许往上走，否则会有重复； 
bool book_2[6][6];
int parent[13];//并查集
void dfs_2(int x,int y){
    for(int i=0;i<4;i++){
    int dx=x+to[i][0];int dy=y+to[i][1];if(dx<0||dx>2||dy<0||dy>3||book_2[dx][dy]||book[dx][dy]==0){
    continue;}book_2[dx][dy]=true;dfs_2(dx,dy);}
}
bool judge(){
    memset(book,0,sizeof(book)) ;int dx,dy;int cnt;for(int i=0;i<5;i++){
     //把五个点标为1； dx=a[i]/4;dy=(a[i])%4;book[dx][dy]=1;}cnt=0;memset(book_2,false,sizeof(book_2));for(int i=0;i<3;i++){
    for(int j=0;j<4;j++){
    if(book[i][j]==1&&book_2[i][j]==false){
    dfs_2(i,j);cnt++;}}}if(cnt==1){
    return true;}else{
    return false;}// for(int i=0;i<=3;i++){
    
// for(int j=1;j<=4;j++){
    
// if(book[i][j]==1){
    
// if(book[i-1][j]==0&&book[i][j-1]==0&&book[i+1][j]==0&&book[i][j+1]==0){//这个方法是有问题的 
// return false;
// }
// }
// }
// }}
void dfs( int step,int p){
    if(step==5){
     //01234都放好了 if(judge() ){
    //判断是否符合题意
// for(int i=0;i<3;i++){
    
// for(int j=0;j<4;j++){
    
// cout<<book[i][j]<<" ";
// }
// cout<<endl;//调试的时候遇到换行就暂停 
// } 
// cout<<endl;
// for(int i=0;i<5;i++){
    
// cout<<a[i]<<" ";
// }
// cout<<endl<<endl;ans++;}return;}for(int i=p;i<=12-(5-step);i++){
      a[step]=i;dfs(step+1,i+1);}}int main(){
    dfs(0,0);cout<<ans<<endl;
}