搜索（dfs和bfs）

深度优先搜索

P1025 数的划分

https://www.luogu.org/problemnew/show/P1025

//为了保证任意两个方案不相同(不考虑顺序)，可以用last标记上一个数，下一个数不小于它即可 

//考虑到i不可能取到n，因为k>=2。然后sum是当前的和，sum+i*(k-cur),这是最小的情况，如果大于了就不必算了（这一步剪枝特别重要）

#include<bits/stdc++.h>
using namespace std;
int n,k,ans;

void dfs(int last,int sum,int cur)//为了保证任意两个方案不相同(不考虑顺序)，可以用last标记上一个数，下一个数不小于它即可
{
    if(sum>n)
        return;

    if(cur==k)
    {
        if(sum==n) ans++;
        return;
    }
    //考虑到i不可能取到n，因为k>=2。然后sum是当前的和，sum+i*(k-cur),这是最小的情况，如果大于了就不必算了。
    for(int i=last;sum+i*(k-cur)<=n;i++)
    {
        dfs(i,sum+i,cur+1);
    }

}

int main()
{
    scanf("%d%d",&n,&k);
    dfs(1,0,0);
    printf("%d",ans);
}
           

P1433 吃奶酪

https://www.luogu.org/problemnew/show/P1433

这是我最有感想的一道题的了。我看着它慢慢的AC数量越来越多。首先，剪枝!!!,我虽然一直知道要使用剪枝，但是我没有想到哪里剪，结果就超时了好几个点。后来我想到，如果当前的距离已经比前面算过的距离最小值更大了，就不必再算了，因为我们要找的是最小值。然后，我一直在第五个点超时了。参考了题解，第一次发现题解和我的代码有95%的相似度，我特别开心，一下就找到不同了。我在存最小值时，我想的是把每一个答案存在priority_queue里面，最后输出最小值即可，然后每次判断时，判断是否大于了ans.top()，这样的话，确实比较麻烦。如果直接用ans=min(ans,s)，这样不是更简单吗？记住了，以后求最小值的话，就这样做。 

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
double ax[16],ay[16];
int n;
//priority_queue<double,vector<double>,greater<double> > ans;//从小到大
int vis[16];//判断这个点是否访问过
double as[16][16];
double ans=1231234424.0;//保证比每一条路径都要长
double dis(double x1,double y1,double x2,double y2)
{
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
void dfs(int step,int pos,double s)//pos代表当前编号，s代表距离总和
{
     if(s>ans)
        return;
      //if(!ans.empty()&&s>ans.top())
       // return;
    if(step==n)
    {
        //ans.push(s);
        ans=min(ans,s);
        return;
    }

    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            vis[i]=1;
            dfs(step+1,i,s+as[pos][i]);
            vis[i]=0;
        }
    }
}
int main()
{
    scanf("%d",&n);
    int te=0;
    for(int i=1;i<=n;i++)
    {
        cin>>ax[i]>>ay[i];

    }
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=n;j++)
        {
            if(i==j)
              as[i][j]=0;
            else
              as[i][j]=dis(ax[i],ay[i],ax[j],ay[j]);
        }
    }
    vis[0]=1;
    dfs(0,0,0);
  //  double f=ans.top();
    printf("%.2f\n",ans);
    return 0;
}
           

滑雪（记忆化搜索）

https://www.luogu.org/problemnew/show/P1434

用一个额外的数组记录每个位置的最长步数，在搜索时如果遇到已经知道该位置的最长步数就返回该位置的最长步数，节省搜索时间。 

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int a[105][105];
int h[105][105];
int n,m;
int X[4]={0,0,1,-1};
int Y[4]={1,-1,0,0};
int dfs(int x,int y)
{
    if(h[x][y])
        return h[x][y];//该点的最长路已经计算过了，直接返回即可。
    //没有计算过，直接赋值为1，1个数长度为1
    h[x][y]=1;
    for(int i=0;i<4;i++)
    {
        int newx=x+X[i];
        int newy=y+Y[i];
        if(newx>n||newy>m||newx<1||newy<1)
           continue;
        if(a[newx][newy]<a[x][y])
        h[x][y]=max(h[x][y],1+dfs(newx,newy));
    }
    return h[x][y];


}
int ans=0;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);

        }

    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            ans=max(ans,dfs(i,j));

        }

    }
    cout<<ans<<endl;
    return 0;
}
           

数字三角形

https://www.luogu.org/problemnew/show/P1118

解答：遇到这种题，不是使劲的想怎么做怎么做，而要亲自操练，找到规律。

假设n为一个比较小的数(比如，按样例，4)，设第一行的n个数分别为a,b,c,...(我这里是a,b,c,d)，然后模拟加一下，就会发现sum是……

如果n为4，那么sum是a+3b+3c+d。

如果n为5，那么sum是a+4b+6c+4d+e。

如果n为6，那么sum是a+5b+10c+10d+5e+f。

而这个系数，恰恰是杨辉三角数，

可以理解为通通靠左对齐，那么递推式为：

在这里，如果n为4的话，就可以算出a[4][1]=1,a[4][2]=3,a[4][3]=3,a[4][4]=1;

所以，ac代码为：

#include<bits/stdc++.h>
using namespace std;
int a[13][13];
int vis[13];
int n,sum;
int g[13];
int flag=0;
void display()
{
    for(int i=1;i<=n;i++)
    {
        cout<<g[i]<<" ";
    }
    cout<<endl;
}
void dfs(int step,int ans)
{
    if(flag||ans>sum)
        return;//我没有剪枝，所以超时了。
    if(step==n+1&&ans==sum){
       display();
        flag=1;//标记
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(!vis[i])
        {
            g[step]=i;
            vis[i]=1;
            dfs(step+1,ans+i*a[n][step]);
            vis[i]=0;
        }
    }
}
int main()
{
    scanf("%d%d",&n,&sum);
    a[1][1]=1;
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j<=i;j++)
        {
            a[i][j]=a[i-1][j-1]+a[i-1][j];//杨辉三角递推式
        }
    }
    dfs(1,0);
    return 0;
}
           

小雨的矩阵

https://ac.nowcoder.com/acm/contest/949/E

很明显很简单的一道搜索题，我为什么要做笔记呢，因为我的dfs参数写的不对，我没有权值的这个参数，以后要注意，什么在变，就要以什么为参数，代码会很简单。 

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int n;
int a[10][10];
//int vis[10][10];
set<int> ans;
void dfs(int x,int y,int num)
{
    if(x==n&&y==n)
    {
        ans.insert(num);
        return;
    }
    if(x>n||y>n||x<1||y<1)
        return;
    dfs(x+1,y,num+a[x+1][y]);//往下走
    dfs(x,y+1,num+a[x][y+1]);//往右走

}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }

    dfs(1,1,a[1][1]);
    cout<<ans.size()<<endl;
    return 0;
}
           

p1141 01迷宫

https://www.luogu.org/problemnew/show/P1141

仔细一想，既然一个位置能到达另一个位置，那么反过来一样能达到，因此，可以把一个位置能到达的所有位置看成是一个连通块，在一个连通块内，任何位置所到达的格子一样，这样一来，把连通块的位置都进行标记，再搜索没标记的，再看成一个连通块，直至所有位置搜索完

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1010;
int  mapp[MAXN][MAXN];
bool vis[MAXN][MAXN];
int ans[MAXN][MAXN];
int sum[1000010];//此处需注意大小，以防止超出
int setp=0;
int n,m;
int dx[]= {1,-1,0,0};
int dy[]= {0,0,1,-1};
void dfs(int i,int j,int k)
{
    setp++;
    ans[i][j]=k;
    vis[i][j] = true;
    for (int l = 0; l <4 ; ++l)
    {
        int kx = i + dx[l];
        int ky = j + dy[l];
        if (kx >= 0 && kx < n && ky >= 0 && ky < n && mapp[kx][ky] ^ mapp[i][j] && !vis[kx][ky])
        {
            dfs(kx, ky, k);
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0; i<n; i++)
        for(int j=0; j<n; j++)
        {
            scanf("%1d",&mapp[i][j]);
        }
    memset(vis,false,sizeof(vis));
    int k=0;
    for (int i=0; i<n; i++)
    {
        for (int j = 0; j <n ; ++j)
        {
            if(!vis[i][j])
            {
                dfs(i,j,k);
                sum[k]=setp;//第k个连通块的步数
                k++;
                setp=0;
            }
        }
    }
    int x,y;
    for (int j = 0; j <m ; ++j)
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",sum[ans[x-1][y-1]]);
    }
    return 0;
}
           

N皇后

洛谷p1219    https://www.luogu.org/problemnew/show/P1219

这道题利用回溯法，我做的时候，对于我的难点是：N皇后问题要求不准同一行，同一列，以及不能是同一斜线。斜线这里我不会考虑。因为要考虑左斜线和右斜线。

我看了题解后，找到了一个规律，如下：

右斜线（即一条从右上到左下的对角线，其上的棋子坐标满足了x+y为一定值）

左斜线（即一条从左上 到右下的对角线，其上的棋子坐标满足了x-y为一定值，为了避免负数坐标的出现，所以可以设置为x-y+n）

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int r[20],c[20],zl[50],rl[50];
int n;
int sum=0;
void print()
{
    if(sum<3)
    {
        for(int i=1;i<=n;i++)
        {
            cout<<r[i]<<" ";

        }
        cout<<endl;
    }
    sum++;
}
void dfs(int i)
{
    if(i>n)
    {
        print();
        return;
    }
    for(int j=1;j<=n;j++)//j代表列
    {
        if(!c[j]&&!zl[i+j]&&!rl[i-j+n])
        {
            r[i]=j;//i行 为j列占了
            c[j]=1;
            zl[i+j]=1;
            rl[i-j+n]=1;
            dfs(i+1);
            c[j]=0;
            zl[i+j]=0;
            rl[i-j+n]=0;
        }
    }
}
int main()
{

    scanf("%d",&n);
    dfs(1);
    cout<<sum<<endl;
    return 0;
}
           

单词接龙 p1019

https://www.luogu.org/problemnew/show/P1019

解题思路：DFS+字符串处理

我觉得字符串处理这里还算较难，这里用mx函数来算第i个编号和第j个编号的重叠部分的长度。自己模拟就可以懂。return s[x].size() -kx,是找出来的规律。 

#include<bits/stdc++.h>
using namespace std;
#define ll long long
string s[30];//存储的字符串
int a[30][30];//用这个来表示第i个编号的字符串和第j个编号的字符串的重叠部分
int mx(int x,int y)
{
    bool flag=true;
    int ky=0;
    for(int kx=s[x].size()-1;kx>=0;kx--)
    {
        for(int k=kx;k<s[x].size();k++)
        {
            if(s[x][k]!=s[y][ky++])
            {
                flag=false;
                break;
            }
        }
        if(flag==true)
        {
            return s[x].size()-kx;
        }
        ky=0;
        flag=true;
    }
    return 0;
}
int n;
char ch;
int vis[30];//判断单词的使用频率
int ans=-1;//答案
int an=0;//每次搜到的当前最长串
void dfs(int pos)
{
    bool flag=false;
    for(int i=1;i<=n;i++)
    {
        if(vis[i]>=2)//使用了两次及以上就跳过
            continue;
        if(a[pos][i]==0)
            continue;//两单词之间没有重合部分就跳过
        if(a[pos][i]==s[pos].size()||a[pos][i]==s[i].size())
            continue;//如果前后是包含关系的话，就不符合要求，则跳过
        an+=s[i].size()-a[pos][i];//两单词合并再减去重合部分
        vis[i]++;
        flag=true;//标记一下当前已经成功匹配到一个可以连接的部分
        dfs(i);
        an-=s[i].size()-a[pos][i];//回溯
        vis[i]--;
        flag=false;
    }
    if(flag==false)//说明不能再找到任何一个单词可以相连了
       ans=max(ans,an);//更新ans
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
    }
    cin>>ch;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            a[i][j]=mx(i,j);
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(s[i][0]==ch)//如果有，就可以以这个单词为头开始搜索
        {
            vis[i]++;
            an=s[i].size();//更新当前串长度
            dfs(i);
            vis[i]=0;//消除影响
        }
    }
    cout<<ans<<endl;

}
           

迷宫P1605

https://www.luogu.org/problemnew/show/P1605

解答：这里在设置障碍的地方，我就直接用vis[][]=1，这样“已访问”也可以让代码不继续访问，达到了是障碍的效果，vis[][]还有一个效果就是只能访问一次。这道题我最开始只得了70分，因为我忽略了一个问题，vis起点应该为1啊，不然会重复计算多次的。 

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
const int maxn=30;
int n,m,T;
int kx[4]= {0,0,1,-1};
int ky[4]= {1,-1,0,0};
int vis[6][6];
struct node
{
    int x;
    int y;
} st,en,a[maxn];
int ans=0;
void dfs(int sx,int sy)
{
    if(sx==en.x&&sy==en.y)
    {
        ans++;
        return ;
    }

    for(int i=0; i<4; i++)
    {
        sx+=kx[i];
        sy+=ky[i];
        if(sx>n||sy>m||sx<1||sy<1||vis[sx][sy])
        {
            sx-=kx[i];
            sy-=ky[i];
            continue;
        }
        vis[sx][sy]=1;
        dfs(sx,sy);
        vis[sx][sy]=0;
         sx-=kx[i];
         sy-=ky[i];
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&T);
    scanf("%d%d%d%d",&st.x,&st.y,&en.x,&en.y);
    for(int i=0; i<T; i++)
    {
        scanf("%d%d",&a[i].x,&a[i].y);
        int t1=a[i].x,t2=a[i].y;
        vis[t1][t2]=1;
    }
    int xx=st.x,yy=st.y;
    vis[xx][yy]=1;//这里是关键，我就错在这，应该在最开始就把起点设为已经访问，不然会重复访问多次
    dfs(st.x,st.y);
    cout<<ans<<endl;
    return 0;
}
           

p1101单词方阵

https://www.luogu.org/problemnew/show/P1101

#include <bits/stdc++.h>
using namespace std;
const int maxn=100+10;
struct node
{
    int x,y;
} c[maxn]; //记录路径
char fz[maxn][maxn],stand[]="yizhong";//fz保存单词矩阵，stand保存保准的“yizhong”便于匹配
int vis[maxn][maxn];//保存路径，是否该点为答案
int dir[][2]= {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}}; //八向的常量数组
void dfs(int x,int y,node c[],int k,int cur)
{
    if(cur==7)
    {
        for(int i=0; i<7; i++)
            vis[c[i].x][c[i].y]=1;
    }
    else
    {
        int dx=x+dir[k][0];//沿着正确的k方向搜索
        int dy=y+dir[k][1];
        if(cur==6||fz[dx][dy]==stand[cur+1])//要判断cur=6是因为cur+1在cur=6时已经超范围了
        {
            c[cur].x=x;
            c[cur].y=y;
            dfs(dx,dy,c,k,cur+1);
        }
    }
}
int main()
{

    int n;
    scanf("%d",&n);
    for(int i=0; i<n; i++)
        scanf("%s",fz[i]);
    memset(vis,0,sizeof(vis));
    for(int i=0; i<n; i++) //搜索y，i相连的可能的方向k，以k为方向进行DFS
    {
        for(int j=0; j<n; j++)
        {
            if(fz[i][j]=='y')
                for(int k=0; k<8; k++)
                {
                    int x=i+dir[k][0];
                    int y=j+dir[k][1];
                    if(fz[x][y]=='i')
                        dfs(i,j,c,k,0);
                }
        }
    }
    for(int i=0; i<n; i++) //输出结果
    {
        for(int j=0; j<n; j++)
            if(vis[i][j]) printf("%c",fz[i][j]);
            else printf("*");
        printf("\n");
    }
    return 0;
}
           

p1092虫食算

https://www.luogu.org/problemnew/show/P1092 

#include<bits/stdc++.h>
#define maxn 30
int n,flag[maxn];
char s[4][maxn];
bool use[maxn];
int id(char ch)//将字符串转换为数字
{
    return ch-'A'+1;
}
void dfs(int x,int y,int t)//x代表行，y代表列，t代表进位
{
    if (y==0) //从上到下，从右到左，y==0表示搜到了最后一列
    {
        if (t==0)//最后一列不能有进位，如果进了以为则第三个字符串会比其他两个字符串长一位
        {
            for (int i=1; i<n; i++) //如果满足条件，就输出
                printf("%d ",flag[i]);//输出
            printf("%d\n",flag[n]);//输出
            exit(0);    //相当于return  0;程序结束
        }
        return;//返回
    }
    for (int i=y-1; i>=1; i--) //剪枝1,y代表列
    {
        int w1=flag[id(s[1][i])];//w1表示第一行字符串代表的数字，第1行第i列
        int w2=flag[id(s[2][i])];//w2表示第二行字符串代表的数字，第2行第i列
        int w3=flag[id(s[3][i])];//w3表示第三行字符串代表的数字，第3行第i列
        if (w1==-1||w2==-1||w3==-1) //如果这个位置上还没被赋值，就返回
            continue;
       if ((w1+w2)%n!=w3&&(w1+w2+1)%n!=w3)
            return;    //如果无论进位与否，都不能整除对应的w3就说明字符串不匹配，直接return ;


    }
    if (flag[id(s[x][y])]==-1) 如果这个位置上还没被赋值，就进行赋值操作
    {
        for (int i=n-1; i>=0; i--) //倒着枚举更快
            if (!use[i]) //如果这个数没有用过
            {
                if (x!=3) //且不是最后一行
                {
                    flag[id(s[x][y])]=i;//就将这个位置赋上值
                    use[i]=1;//标记这个数用过
                    dfs(x+1,y,t);//继续搜索下一行
                    flag[id(s[x][y])]=-1;//还原
                    use[i]=0;//还原
                }
                else //当x==3时
                {
                    int w=flag[id(s[1][y])]+flag[id(s[2][y])]+t;//两个数加上它们的进位
                    if (w%n!=i)
                        continue;
                    use[i]=1;
                    flag[id(s[3][y])]=i;//赋值，标记这个数用过
                    dfs(1,y-1,w/n);//搜索下一列，进位需要改变
                    use[i]=0;
                    flag[id(s[3][y])]=-1;//还原
                }
            }
    }
    else //如果这个位置上已经被赋值了
    {
        if (x!=3) //继续搜索
            dfs(x+1,y,t);
        else
        {
            int w=flag[id(s[1][y])]+flag[id(s[2][y])]+t;
            if (w%n!=flag[id(s[3][y])]) //剪枝 2
                return;
            dfs(1,y-1,w/n);//搜索下一列，进位需要改变
        }
    }
}
int main()
{
    scanf("%d",&n);//读入n,代表n进制等......
    for (int i=1; i<=3; i++)
        scanf("%s",s[i]+1);//读入3行字符串
    memset(flag,-1,sizeof(flag));//将所有位置标记为未赋值
    dfs(1,n,0);//从右往左，上往下搜索，所有从第n列，第1行开始
    return 0;//结束
}
           

广度优先搜索

填涂颜色p1162

https://www.luogu.org/problemnew/show/P1162

这道题在判断坐标是否越界时，一定要注意：虽然我的坐标是1~n，但是在判断时，应该是判断<0和> n+1;因为要在外包一层来计算，不然会出错。而且初始化dfs时，是dfs(0,0),不然会漏掉。

比如：

不在外围算的话，我的三角形圈的部分就接触不到，会误以为被包围了，实则不是。 

#include <bits/stdc++.h>
using namespace std;
int a[32][32],b[32][32];
int dx[4]= {-1,1,0,0};
int dy[4]= {0,0,-1,1}; //第一个表示不动，是充数的，后面的四个分别是上下左右四个方向
int n,i,j;
void dfs(int p,int q)
{
    int i;
    if (p<0||p>n+1||q<0||q>n+1||a[p][q]!=0)//相当于外围围了一个套子，所以判断0，n+1；不然外围的算不到
        return;//如果搜过头或者已经被搜过了或者本来就是墙的就往回
    a[p][q]=1;//染色,这里的染色是把没有围住的点染色，太强了的方法。

    for (i=0; i<=3; i++)
        dfs(p+dx[i],q+dy[i]); //向四个方向搜索
}
int main()
{
    cin>>n;
    for (i=1; i<=n; i++)
        for (j=1; j<=n; j++)
        {
            cin>>b[i][j];//其实不拿两个数组也可以，不过我喜欢啦
           if (b[i][j]==0)
                a[i][j]=0;
            else
                a[i][j]=1;//a[i][j]=2也可以，只要不等于0就行
        }
    dfs(0,0);//搜索,必须从0,0开始搜，不然最外围的有些0可能搜不到
    for (i=1; i<=n; i++)
    {
        for (j=1; j<=n; j++)
            if (a[i][j]==0)
                cout<<2<<' ';//如果染过色以后i，j那个地方还是0，说明没有搜到，就是周围有墙，当然就是被围住了，然后输出2
            else
                cout<<b[i][j]<<' ';//因为被染色了，本来没有被围住的水和墙都染成了1，所以就输出b[i][j]
        cout<<'\n';//换行
    }
}
           

子串变换p1032 

https://www.luogu.org/problemnew/show/P1032 

解答：这道题我拿着的时候完全不会。我学到了很多，用string 定义的字符串，可以用s.find(a)，找到a在s中第一次出现的位子，如果不存在则返回1.   另外用string类的replace函数。比如ss.replace(m,sa[i].size(),sb[i]);//在ss中用子串sb[i]替换s里第一次出现的子串sa[i]。  

这道题还要注意剪枝，以及p和bb是对应的，该个字符串对应的步数。

  s[m]='~';//将s里子串sa[i]的第一次出现位子随便换成另一种无关的字符，这样就可以查找到s里子串sa[i]的下一个出现位子

这一步操作也比较厉害，因为可能存在多个这种子串。

#include<bits/stdc++.h>
using namespace std;
queue<int> bb;
queue<string> q;
string sa[8],sb[8];//最多六次转换
string a,b;//起始字符串，终止字符串
int len;
map<string,int> map1;//用map存放已经宽搜过的字符串，用来判重
int bfs()
{
    q.push(a);
    bb.push(0);
    int m;
    string s,ss;
    while(!q.empty()&&bb.front()<10&&q.front()!=b)
    {

        if(map1[q.front()]==1)
        {
            //剪枝，如果当前字符串已经广搜过了，就弹出，进入下一次循环
            q.pop();
            bb.pop();
            continue;
        }
        map1[q.front()]=1;
        for(int i=1; i<=len; i++)
        {
            s=q.front();
            while(1)
            {
                m=s.find(sa[i]);//找到子串sa[i]的第一次出现的位子
                if(m==-1)
                {
                    //如果没有找到，就结束循环
                    break;
                }
                ss=q.front();
                ss.replace(m,sa[i].size(),sb[i]);//在ss中用子串sb[i]替换s里第一次出现的子串sa[i]
                q.push(ss);
                bb.push(bb.front()+1);
                s[m]='~';//将s里子串sa[i]的第一次出现位子随便换成另一种无关的字符，这样就可以查找到s里子串sa[i]的下一个出现位子

            }
        }
        q.pop();//将操作过的字符串弹出队列
        bb.pop();//操作过的字符串已经用过的步数一起弹出


    }
    if(q.empty()==1||bb.front()>10)
        return -1;
    else
        return bb.front();

}
int main()
{
    cin>>a>>b;
    len=1;
    while(cin>>sa[len]>>sb[len])
        len++;
    len--;//因为多加了一次，减掉一次后才是正确的次数
    int k=bfs();
    if(k==-1)
    {
        cout<<"NO ANSWER!"<<endl;

    }
    else
        cout<<k<<endl;
    return 0;
}
           

牛客多校第九场 D （折半搜索）

https://ac.nowcoder.com/acm/contest/889/D

题意：就是一个序列去使一个子序列和为给定和

题解：数据特别大

The first line contains two integers, which are n(1 <= n <= 36) and s(0 <= s < 9 * 10^18)

The second line contains n integers, which are {ai}(0 < ai < 2 * 10^17).

如果直接搜这36个数字是 O（2^36）复杂的，但只有1s时间，所以折半搜索，降一半复杂度O（2*2^18）

先处理一半18位，记录搜到的所有子集和以及数字编号，再搜另一半和时候的二分找第一次处理的和加起来满足给定和就好

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e6+5;//因为我们采用折半搜索，把数组分为前后两个部分，而复杂度2^20对应大概1e6
//这道题方法为前后分为两个部分来做，不然复杂度就为2^36，肯定超了
int n,N;
ll a[40];
int vis[40];
ll sum;
int cnt=0;
struct node
{
    ll w;
    int kk[20];//因为n<=36,一半的话只要大于18就行了

}na[maxn];
bool cmp(node a,node b)
{
    return a.w<b.w;
}
void dfs(int i,ll k)
{
    if(i==N)
    {
        for(int j=0;j<i;j++)
        {
            na[cnt].kk[j]=vis[j];
        }
        na[cnt].w=k;
        cnt++;
        return;

    }
    vis[i]=1;
    dfs(i+1,k+a[i]);
    vis[i]=0;
    dfs(i+1,k);
}
void dfs2(int i,ll k)
{
    if(i==n)
    {
        ll x=sum-k;
        int l=0,r=cnt-1;
        while(l<r)
        {
            int mid=(l+r)>>1;
            if(na[mid].w>=x)
                r=mid;
            else
                l=mid+1;
        }
        if(na[l].w+k==sum)
        {
            for(int j=0;j<N;j++)
                cout<<na[l].kk[j];
            for(int j=N;j<n;j++)
                cout<<vis[j];
             cout<<endl;
        }
        return;

    }
    vis[i]=1;
    dfs2(i+1,k+a[i]);
    vis[i]=0;
    dfs2(i+1,k);
}
int main()
{
    scanf("%d %lld",&n,&sum);
    for(int i=0;i<n;i++)
        scanf("%lld",&a[i]);
    N=n/2;
    dfs(0,0);
    sort(na,na+cnt,cmp);
    dfs2(N,0);
    return 0;
}
           

杭电多校第10场签到题 （Block Breaker )

https://vjudge.net/contest/322382#problem/I

题意:

有n*m个块装在一个框内，以左上角为原点，竖直向下为x正半轴，水平向右为y正半轴建立坐标系，快和块之间和块和框架之间会有摩擦力，原题意说：如果一个块的左边或右边至少掉了一个，以及前方或后方至少掉了一个，它就会掉。也就是说，一个块如果上下或左右有方块或框架，则他们之间可以被固定住，否则就会落下

有q次操作，每次操作会将(x,y)位置的块敲掉，问每次操作最多能掉下多少方块，如果操作的位置没有方块则输出0

思路:

可以模拟，用dfs或bfs都行，这里选择dfs，从操作位置开始搜索，如果搜索超出了边界或搜到了空位置就返回，否则就把当前位置置为空且答案+1，

从当前位置向周围检查，如果超出边界就跳过（因为我把框架也当成方块，但这个方块必须被固定而不能落下，所以检查到边界时跳过）否则如果检查到的方块不为空且他上下没有对应方块且左右没有对应方块就搜索这个检查到的位置

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int maxn=2005;
int a[maxn][maxn];
int n,m,q;
int ans=0;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
bool check(int x,int y)  ///如果上下有对应方块或左右有对应方块则返回1（则不会掉落），否则返回0（则会掉落）
{
    return (a[x-1][y]&&a[x+1][y])||(a[x][y-1]&&a[x][y+1]);//因为只有在左或右边没有块、上或下边没有块才会掉落

}
void dfs(int x,int y)
{
    if(!a[x][y]||x<1||x>n||y<1||y>m)//如果它已经掉落了，或者坐标超出范围了，就返回
        return;
    a[x][y]=0;//不然访问的这个点一个是可以掉落的
    ans++;//则答案加一
    for(int i=0;i<4;i++)
    {
        int newx=x+dir[i][0];
        int newy=y+dir[i][1];
        if(newx<1||newx>n||newy<1|newy>m)
            continue;
        if(!check(newx,newy)&&a[newx][newy])//这里就是说如果这个点可以掉落，且它还未被标记，就深搜
            dfs(newx,newy);
    }
}
int main()
{
    int T;
    scanf("%d",&T);
   // int ans=0;
    while(T--)
    {
       // int n,m,q;
        scanf("%d%d%d",&n,&m,&q);
        for(int i=0;i<=n+1;i++)
        {
            for(int j=0;j<=m+1;j++)///把边界也处理为方块，不过边界方块是固定的不能掉落
            {
                a[i][j]=1;//固定
            }
        }
        for(int i=1;i<=q;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            ans=0;
            dfs(x,y);
            printf("%d\n",ans);

        }
    }
    return 0;
}
           

迷宫问题

#include <iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int maxn=1000;
int X[]={0,0,-1,1};
int Y[]={1,-1,0,0};
int n;
int step=0;
struct node
{
    int x;
    int y;
    int step;
}S,T,Node;//S为起点，T为终点，Node为临时结点
char mig[maxn][maxn];
bool inq[maxn][maxn]={false};
bool check(int x,int y)
{
    
    if(mig[x][y]=='#'||inq[x][y]==true)
    {
        return false;
    }
    return true;
}
int BFS()
{
    queue<node> Q;
    Q.push(S);
    while(!Q.empty())
    {
        node top=Q.front();
        Q.pop();
        if(top.x==T.x&&top.y==T.y)
        {
            return top.step;
        }
        for(int i=0;i<4;i++)
        {
            int newX=top.x+X[i];
            int newY=top.y+Y[i];
            if(newX>=n) newX=0;
            if(newX<0) newX=n-1;
            if(newY>=n) newY=0;
            if(newY<0) newY=n-1;
            if(check(newX,newY))
            {
                
                Node.x=newX;
                Node.y=newY;
                Node.step=top.step+1;
                Q.push(Node);
                inq[newX][newY]=true;
 
            }
        }
    }
    return -1;//无法到达终点
}
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        getchar();//过滤到每行后的换行符
        for(int j=0;j<n;j++)
        {
            mig[i][j]=getchar();
            if(mig[i][j]=='S'){
                S.x=i;
                S.y=j;
            }
            if(mig[i][j]=='E'){
                T.x=i;
                T.y=j;
            }
        }
        mig[i][n+1]='\0';
    }
   // scanf("%d%d%d%d",&S.x,&S.y,&T.x,&T.y);
    S.step=0;//初始化起点的层数为0，即S到S的最小步数为0
 
 
    cout <<BFS()<< endl;
    return 0;
}