难点是如何实现每次都搜索分支数最少的？
y总这里实现了一种很妙的方法
利用二进制表示每行每列每个九宫格的状态交后计数即可

#include<iostream>
#include<cstring>
using namespace std;
const int N=9,M=1<<N;
int count[M],map[M];
int ha[N],le[N],col[3][3];
char sta[100];
int cnt;

int lowbit(int x)
{
    return x&-x;
}

int get(int x,int y)
{
    return ha[x]&le[y]&col[x/3][y/3];
}

void draw(int x,int y,int t,bool falg)
{
    if(falg)sta[x*N+y]=t+'1';
    else sta[x*N+y]='.';
    int v;
    if(falg)v=1<<t;
    else v=-1<<t;
    ha[x]-=v;
    le[y]-=v;
    col[x/3][y/3]-=v;
}
bool dfs(int sum)
{
    if(sum==0)return true;
    int miv=10,x,y;
    for(int i=0;i<N;i++)
    for(int j=0;j<N;j++)
    {
        if(sta[i*N+j]=='.')
        {
            int tt=get(i,j);
            if(count[tt]<miv)
            {
                x=i,y=j;
                miv=count[tt];
            }
        }
    }
    int tt=get(x,y);
    for(int i=tt;i;i-=lowbit(i))
    {
        int t=map[lowbit(i)];
        draw(x,y,t,true);
        if(dfs(sum-1))return true;
        draw(x,y,t,false);
    }
    return false;
}

void init()
{
    for(int i=0;i<N;i++)ha[i]=le[i]=(1<<N)-1;
    for(int i=0;i<3;i++)
    for(int j=0;j<3;j++)
    col[i][j]=(1<<N)-1; 
}
int main()
{
    for(int i=0;i<N;i++)map[1<<i]=i;
    for(int i=0;i<1<<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            if(i>>j&1)count[i]+=1;
        }
    }
    while(cin>>sta,sta[0]!='e')
    {
        init();
        int cnt=0;
        for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
        {
            if(sta[i*N+j]!='.')
            {
                int t=sta[i*N+j]-'1';
                draw(i,j,t,true);
            }
            else cnt++;
        }
        dfs(cnt);
        cout<<sta<<endl;
    }
    return 0;
}

二刷提高课，题解目录在这里— 提高课的题解目录

这里注意一下搜索顺序是从重猫到轻猫因为这样选择数量较少（会经常用到）
这里我们并不纠结每个组内会不会有约束关系所以我们没与必要用组来枚举猫
只需一只一只枚举即可

#include<iostream>
#include<algorithm>
using namespace std;
const int N=20;
int a[N],sum[N];
int n,k;
int res=20;
void dfs(int u,int r)
{
    if(r>=res)return;
    if(u==n+1)
    {
        res=r;
        return;
    }
    for(int i=0;i<r;i++)
    {
        if(sum[i]+a[u]<=k)
        {
            sum[i]+=a[u];
            dfs(u+1,r);
            sum[i]-=a[u];
        }
    }
    sum[r]=a[u];
    dfs(u+1,r+1);
    sum[r]=0;
}
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>a[i];
    sort(a+1,a+1+n);
    reverse(a+1,a+1+n);
    dfs(1,0);
    cout<<res;
    return 0;
}

这题比较难想到搜索顺序，我们每次都只搜最后一组
来向后遍历所有的点看是否任然有能加进去的点，当没有会新开个组并让前面没有加进去的点重新遍历
因为每次遍历最后一组保证了我们能加肯定加，也就是当一个点能加进去没有必要为了它重开一个
但是这样为什么一定能搜到全部的可能呢？
答案是可以的，无论哪种合法方案我们都可以在我们的枚举结果中找到，不会缺少
因为我们枚举了在最后一层的所有合法可能，而最终答案亦是合法的
这也就告诉我们一个枚举技巧：我们可以确定枚举顺序，当中间状态过多时我们可以只选择枚举最后一组

#include<iostream>
using namespace std;
const int N=15;
int greap[N][N];
bool st[N];
int a[N];
int n;
int res=10;
int gcd(int a,int b)
{
    if(!b)return a;
    else return gcd(b,a%b);
}
bool check(int g[],int l,int x)
{
    for(int i=0;i<l;i++)
    {
        if(gcd(g[i],a[x])!=1)return false;
    }
    return true;
}
void dfs(int u,int ur,int lo,int sta)
{
    if(u>res)return;
    if(lo==n)res=u;
    bool falg=true;
    for(int i=sta;i<n;i++)
    {
        if(!st[i]&&check(greap[u],ur,i))
        {
            st[i]=true;
            greap[u][ur]=a[i];
            dfs(u,ur+1,lo+1,i+1);//当不是一个组的时候一直时像后遍历一种优化
            st[i]=false;
            falg=false;
        }
    }
    //只有当无法加入状态才会重新开一组
    if(falg)dfs(u+1,0,lo,0);//而开新组的时候总是从零开始
}
int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    cin>>a[i];
    dfs(1,0,0,0);
    cout<<res;
    return 0;
}

二刷提高课，题解目录在这里— 提高课的题解目录

难度应该是如何将所有的状态搜索到
并且如何取搜索
因为我们搜索的时候会重复判断是否可以搜索
所以这里先预处理一下可以接龙的最短重复位置
然后直接爆搜即可

#include<iostream>
#include<cstring>
using namespace std;
const int N=21;
int n;
string word[N];
int g[N][N];
int used[N];
int res;
void dfs(string xx,int u)
{
    res=max(res,(int)xx.size());
    used[u]++;
    for(int i=1;i<=n;i++)
    {
        if(g[u][i]&&used[i]<=1)
        {
            dfs(xx+word[i].substr(g[u][i]),i);
        }
    }
    used[u]--;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)cin>>word[i];
    char x;
    cin>>x;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int k=1;k<min(word[i].size(),word[j].size());k++)
            {
                if(word[i].substr(word[i].size()-k)==word[j].substr(0,k))
                {
                    g[i][j]=k;
                    break;
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(word[i][0]==x)
        dfs(word[i],i);
    }
    cout<<res;
    return 0;
}

二刷提高课，题解目录在这里— 提高课的题解目录

其实就是统计一下所走空格的数量，dfs一下即

#include<iostream>
#include<cstring>
using namespace std;
bool st[10][10];
int n,m,s,k,res;
int dx[8]={-1,-1,-2,-2,1,1,2,2};
int dy[8]={2,-2,1,-1,2,-2,1,-1};
void dfs(int x,int y,int z)
{
    if(z==n*m)
    {
        res++;
        return;
    }
    st[x][y]=true;
    for(int i=0;i<8;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(a<0||a>=n||b<0||b>=m)continue;
        if(st[a][b])continue;
        dfs(a,b,z+1);
    }
    st[x][y]=false;

}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        res=0;
        memset(st,0,sizeof st);
        cin>>n>>m;
        cin>>s>>k;
        dfs(s,k,1);
        cout<<res<<endl;
    }
}

二刷提高课，题解目录在这里— 提高课的题解目录

dfs实现flood fill
流水灌溉模型

#include<iostream>
#include<cstring>
using namespace std;
const int N=30;
char g[N][N];
bool st[N][N];
int n,m,x1,y1;
int res;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int dfs(int x,int y)
{
    int q=1;
    for(int i=0;i<4;i++)
    {
        int xx=x+dx[i],yy=y+dy[i];
        if(xx<1||xx>n||yy<1||yy>m)continue;
        if(g[xx][yy]=='#'||st[xx][yy])continue;
        st[xx][yy]=true;
        q+=dfs(xx,yy);
    }
    return q;
}
int main()
{
    while(cin>>m>>n,m||n)
    {
        memset(st,0,sizeof st);
       for(int i=1;i<=n;i++)
       for(int j=1;j<=m;j++)
       {
           cin>>g[i][j];
           if(g[i][j]=='@')
           {
            x1=i;
            y1=j;
           }
       }
       st[x1][y1]=true;
       res=dfs(x1,y1);
       cout<<res<<endl;
    }
    return 0; 
}

二刷提高课，题解目录在这里— 提高课的题解目录

普通的dfs走迷宫
注意数据量，当数据量比较大的时候用bfs比较好

#include<iostream>
#include<cstring>
using namespace std;
const int N=110;
char g[N][N];
int n;
int a,b,c,d;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
bool st[N][N];
bool dfs(int x,int y)
{
    if(g[x][y]=='#'||g[c][d]=='#')return false;
    if(x==c&&y==d)return true;
    st[x][y]=true;
    for(int i=0;i<=3;i++)
    {
        int a1=x+dx[i],b1=y+dy[i];
        if(a1<0||a1>=n||b1<0||b1>=n)continue;
        if(st[a1][b1])continue;
        if(dfs(a1,b1))return true;
    }
    return false;

}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n;
        memset(st,0,sizeof st);
        for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        cin>>g[i][j];
        cin>>a>>b>>c>>d;
        if(dfs(a,b))cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

二刷提高课，题解目录在这里— 提高课的题解目录

八数码问题有解的充要条件是：将八数码顺序展开逆序对的数量必须是偶数！
注意这种字符的启发式函数如何构造
每个点理论应该在的位置与实际所在的位置的哈密顿距离
因为不存在移动一步使得两个棋子到达了自己的位置（因为我们不能交换棋子只能交换x）

#include<iostream>
#include<unordered_map>
#include<queue>
#include<algorithm>
using namespace std;
typedef pair<int ,string>PIS;
string sttar;
int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};
char op[4]={'r','l','u','d'};
int f(string sta)
{
    int res=0;
    for(int i=0;i<9;i++)
    {
        if(sta[i]!='x')
        {
            int tt=sta[i]-'1';//tt是理论距离，i为现实距离
            res+=(abs(tt/3-i/3)+abs(tt%3-i%3));
        }
    }
    return res;
}
string bfs(string star)
{

    string nd="12345678x";
    unordered_map<string,int >hp;
    unordered_map<string,pair<string,char>>pre;
    priority_queue<PIS,vector<PIS>,greater<PIS>>qu;
    qu.push({f(star),star});
    hp[star]=0;
    while(qu.size())
    {
        auto h=qu.top();
        qu.pop();
        string st=h.second;
        if(st==nd)break;
        int x,y;
        for(int i=0;i<st.size();i++)
        {
            if(st[i]=='x')
            {
                x=i/3;
                y=i%3;
                break;
            }
        }
        string bak=st;//下面会改变数值所以需要备份
        for(int i=0;i<=3;i++)
        {
            int a=x+dx[i],b=y+dy[i];
            if(a<0||a>=3||b<0||b>=3)continue;
            swap(st[a*3+b],st[x*3+y]);
            if(!hp.count(st)||hp[st]>hp[bak]+1)
            {
                hp[st]=hp[bak]+1;
                pre[st]={bak,op[i]};
                qu.push({f(st)+hp[st],st});
            }
            swap(st[a*3+b],st[x*3+y]);
        }
    }
    string rs;
    while(star!=nd)
    {
        rs+=pre[nd].second;
        nd=pre[nd].first;
    }
    reverse(rs.begin(),rs.end());
    return rs;
}
int main()
{
    string g;
    for(int i=1;i<=9;i++)
    {
        char x;
        cin>>x;
        g+=x;
        if(x!='x')
        sttar+=x;
    }
    int cnt=0;
    for(int i=0;i<8;i++)
    for(int j=i+1;j<8;j++)
    if(sttar[i]>sttar[j])cnt++;
    if(cnt%2)cout<<"unsolvable";
    else cout<<bfs(g);
    return 0;
}

二刷提高课，题解目录在这里— 提高课的题解目录

此题使用A*算法，一种启发式搜索，每次选取估价函数最小的来进行扩展
这里使用了最短路来作为估价函数（估价函数一般要小于等于真实值）
而如何得到所有点到终点的最短路呢？反向djs即可（注意这种思想）

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N=1010,M=200010;
typedef pair<int ,int >PII;
typedef pair<int, PII> PIII;
int h[N],rh[N],ne[M],de[M],we[M];//反向遍历
int dist[N];
int cnt[N];
int dix,n,m,sta,en,k;
int st[N];
void add(int h[],int a,int b,int c)
{
    de[dix]=b,ne[dix]=h[a],we[dix]=c,h[a]=dix++;
}
void dijstra()
{
    priority_queue<PII,vector<PII>,greater<PII>>q;
    q.push({0,en});
    memset(dist,0x3f,sizeof dist);
    dist[en]=0;
    while(q.size())
    {
        auto hh=q.top();
        q.pop();
        int x=hh.first,y=hh.second;
        if(st[y])continue;
        st[y]=true;
        for(int i=rh[y];~i;i=ne[i])
        {
            int j=de[i];
            if(dist[j]>dist[y]+we[i])
            {
                dist[j]=dist[y]+we[i];
                q.push({dist[j],j});
            }
        }
    }
}
int astar()
{
    priority_queue<PIII,vector<PIII>,greater<PIII>>q;
    q.push({dist[sta],{0,sta}});
    while(q.size())
    {
        auto hh=q.top();
        q.pop();
        int x=hh.second.first,y=hh.second.second;
        cnt[y]++;
        if(cnt[en]==k)return x;
        for(int i=h[y];~i;i=ne[i])
        {
            int j=de[i];
            if(cnt[j]<k)//每个点在路径中最多出现k次（j是最短的次数小于k）
            {
                q.push({x+we[i]+dist[j],{x+we[i],j}});
            }
            //为什么没有等于k，因为如果有等于k的，他会在上面遍历其他的点
            //这里选择等于k那么出队的就是k+1，也就是多了
        }
    }
    return -1;
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    memset(rh,-1,sizeof rh);
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(h,a,b,c),add(rh,b,a,c);
    }
    cin>>sta>>en>>k;
    if(sta==en)k++;
    dijstra();
    cout<<astar();
    return 0;
}

二刷提高课，题解目录在这里— 提高课的题解目录

此题又引入了一个解决问题的思想，双向广搜
当我们从一个方向搜索结果时间复杂度过于高时，可以试用双向广搜
原理就是用空间换时间，记录两边搜索到的结果看是否有重合
还有一点就是我们搜索的时候一定要搜索一层而不是一个（和我们bfs操作类似）每次搜一层
可以大大减小时间消耗（记住这种解决问题的思想）

#include<iostream>
#include<queue>
#include<unordered_map>
using namespace std;
const int N=6;
int n;
string sta,en;
string a[N],b[N];
int solve(queue<string>&q,unordered_map<string,int>&da,unordered_map<string,int>&db, string a[N], string b[N])
{
    //注意这里要遍历一层,而一层的共同点就是遍历的次数da
    int d=da[q.front()];
    while(q.size()&&d==da[q.front()])
    {
        auto t=q.front();
        q.pop();
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<t.size();j++)
            {
                if(t.substr(j,a[i].size())==a[i])
                {
                    string tt=t.substr(0,j)+b[i]+t.substr(j+a[i].size());
                    if(db.count(tt))return da[t]+db[tt]+1;
                    if(da.count(tt))continue;
                    da[tt]=da[t]+1;
                    q.push(tt);
                }
            }
        }
    }
    return 11;

}
int bfs()
{
    if(sta==en)return 0;
    queue<string >qa,qb;
    unordered_map<string ,int >da,db;
    qa.push(sta);
    qb.push(en);
    da[sta]=db[en]=0;
    int step=0;
    while(qa.size()&&qb.size())//优化：每次选择剩余最小的来使得搜索平衡一些
    {
        int t;
        if(qa.size()<qb.size())t=solve(qa,da,db,a,b);
        else t=solve(qb,db,da,b,a);
        if(t<=10)return t;
        if(++step==10)return -1;
    }
    return -1;
}
int main()
{
    cin>>sta>>en;
    while(cin>>a[n]>>b[n])n++;
    int t=bfs();
    if(t==-1)cout<<"NO ANSWER!";
    else cout<<t;
    return 0;
}